A Different 'Center' To A Polygon

In the last post here, we pondered (without nailing to the wall), the problem of finding the point inside a convex polygon which maximizes the minimum angle subtended there by the edges of the polygon. Now, we have something else on similar lines.

Problem: Given a convex polygon, find the point in its interior for which the sum of distances to the vertices of the polygon is least.

Thoughts: The required point need not be the centroid of the polygon.
---------
Example. consider a convex polygon formed by (1) 100 points extremely close to each other - so close that they are separate only at near infinite zoom - near the point x=-1 on the X axis, (2) another 100 points similarly close to each other but near the point x = +1 on the X axis and (3) a single point on the Y axis at Y = 201. Of course, the close by points lie so that the total set of 21 points form a convex polygon - from a distance this polygon looks like a triangle though.

Now, the centroid of this polygon is very close to a point on Y axis: y = +1. this centroid is at a distance 200 from the lone apex point and nearly sqrt(2) distant from the other 200 points. Now, consider the mid point of the base of the polygon, lying between the two point bunches at x = +/-1. This mid point is at distance 201 from the lone apex point but only at distance equal to nearly 1 from the other 200 points. Its distance sum is clearly less than that of the centroid.

------------

It might be interesting to see how this distance sum function varies across the region of the polygon in various cases. If I understand right, Earnshaw's theorem probably implies Sum (reciprocals of distances from vertices) has no proper minimum in the interior (only saddle points). Maybe something similar could be said about the distance sum as well.

Note added on May 23rd: Earnshaw's theorem is, as far as I know, a consequence of the electrostatic potential satisfying Laplace equation. The present problem has a potential that increases linearly with distance from the 'charge' and this *does not* satisfy Laplace equation. Hence there can very well be local maxima and minima for the distance sum function in the interior of the polygon. I know of no case where the *maximum* of the (sum of distances from vertices) is somewhere in the interior of the convex polygon - here we look at only the interior of the polygon and its boundary, not exterior.

Note added on July 5th 2007: Experiments indicate that the point which minimizes the sum of distances from the vertices has a unique position (there are no local minima etc for this distance sum function) . This appears true not only when the vertices are those of a convex polygon - any distribution of points (call them vertices)appears to have this property: a unique point minimizes the sum of the distances from these vertices.

And here is some further perspective from 'Mathworld':
"A convex function is a continuous function whose value at the midpoint of every interval in its domain does not exceed the arithmetic mean of its values at the ends of the interval."
This implies a convex function has to have at most one local minimum in its domain. I remember hearing that distance is a convex funtion (not sure about the proof) and probably, so is the sum of distances. Thus, we could say:
"Given a distribution of vertices on a plane and a point P which varies along any straight line. The sum of the distances from P to the vertices has a unique minimum on its straight line path. And since for P running along *any* straight line path in that plane, the distance sum function has a unique minimum, the function has to have a unique minimum *for the plane as a whole*.

Note added on December 12th and edited on May 26th 2015: If the input polygon is a triangle, this problem is called the Fermat's problem. In this special case, the solution also solves the Steiner tree problem. Coxeter has described this special case in his 'Intro to Geometry' and proved the point is such that all the 3 sides of the triangle subtend 120 degrees there. Note: This solves for triangles the problem (next post here) of finding the interior point that maximizes the least angle subtended by a side of the polygon. And this wikipedia article has more details: http://en.wikipedia.org/wiki/Geometric_median

Question: For any convex polygon, are the interior points that maximizes the min side-subtended angle and minimizes the sum of distances from vertices respectively are same?

Answer: Not necessarily. Consider a regular polygon with very large by finite n vertices. The center maximuizes both the minimual side-subtended angle and the sum of distances from vertices. Now add an n+1th vertex very close to one of the vertices to form an n+1-gon. At the physical center of the polygon (which is essentially unchanged with new vertex), the least side subtended angle will be extremely small. To make this angle compparable to the others, the corresponding center has to be moved very close to the neighborhood of the newly added vertex. But there is no need to move the distance sum center (which is the center of mass)that much if n is large.

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.