A Triangulation Problem
The following problem was posed by Anurag. Thanks to Ramana Rao for his inputs.
--------
Given a convex polygon, how does one choose a point in its interior so that the least angle subtended at this point by the edges of the polygon is a maximum?
--------
Our present line of thought is:
1. Choose a variable point, say P at any location in the interior of the polygon and note the smallest angle subtended by the sides there. Note this side as S.
2. Move P towards this side S - so that the angle subtended by S at P keeps increasing, until the angle subtended by another side S' at the current point equals that subtended by S. Note the present position of P.
3. Now we need to further search in the intersection region of two circles - C passing thru the end points of S and P and circle C', that passes thru the end points of S' and P. Of course during this further search, we also need to see if any other edge of the polygon S'' subtends a smaller angle than S and S'.
The two circles intersect at another point apart from P, say P'. It appears that the best position of the point we need is not necessarily on the line joining P and P' (if we understand right, the reason is related to the locus of points at which two line segments subtend equal angles not being a straight line and being apparently governed by a higher degree polynomial) . So, we might need to search exhaustively the intersection region of the two circles.
To sum up, we do not know the best possible answer and the above method may be seriously flawed!
Note added on July 5th 2007: Experiments indicate that maximizing the minimum angle subtended by the edges of the polygon leads to a unique optimal point. In other words, the function: "minimum among the angles subtended by the edges of the polygon" has a very regular behavior in the interior of the polygon and a single maximum.
--------
Given a convex polygon, how does one choose a point in its interior so that the least angle subtended at this point by the edges of the polygon is a maximum?
--------
Our present line of thought is:
1. Choose a variable point, say P at any location in the interior of the polygon and note the smallest angle subtended by the sides there. Note this side as S.
2. Move P towards this side S - so that the angle subtended by S at P keeps increasing, until the angle subtended by another side S' at the current point equals that subtended by S. Note the present position of P.
3. Now we need to further search in the intersection region of two circles - C passing thru the end points of S and P and circle C', that passes thru the end points of S' and P. Of course during this further search, we also need to see if any other edge of the polygon S'' subtends a smaller angle than S and S'.
The two circles intersect at another point apart from P, say P'. It appears that the best position of the point we need is not necessarily on the line joining P and P' (if we understand right, the reason is related to the locus of points at which two line segments subtend equal angles not being a straight line and being apparently governed by a higher degree polynomial) . So, we might need to search exhaustively the intersection region of the two circles.
To sum up, we do not know the best possible answer and the above method may be seriously flawed!
Note added on July 5th 2007: Experiments indicate that maximizing the minimum angle subtended by the edges of the polygon leads to a unique optimal point. In other words, the function: "minimum among the angles subtended by the edges of the polygon" has a very regular behavior in the interior of the polygon and a single maximum.
posted by R.Nandakumar @ 3:14 AM
3 Comments:
At 5:50 AM,
enu said…
The problem can be looked at as a mechanical system that settles into static equilibrium-- Let the edges of the convex polygon be rigidly fixed. Attach telescopic shafts to each vertex, with their other ends meeting at a point inside the polygon. Now attach coiled (torsion) springs between each adj. pair of telescopic shafts and let it settle down.
Intuitively, this should reach a configuration you want.( But Iam not sure if this is a determinate system. Also vague to me at this pt if there can be many pts at which equilibrium can be attained)
At 12:42 AM,
R.Nandakumar said…
thanks enu.
actually as i mentioned in an appendix to the post, experiments indicate there are no multiple local maxima for our function in the interior of the polygon. there appears to be a single peak.
At 4:06 AM,
R.Nandakumar said…
enu,
the problem in the next post here 'A different center'... does lead to an equilibrium problem like what you describe (coxter's 'intro to geometry').
Post a Comment
<< Home