Finding points inside innermost convex hull - MathOverflow [closed]

Finding points inside innermost convex hull

2010-12-31T11:35:56Z

Given a set of points $S$ on the Euclidean plane, Onion Peeling determines the nested set $H$ of convex hulls on $S$. Define an analytical formula on $S$ which produces a point, not necessarily in $S$, that falls inside the innermost convex hull in $H$. The formula must not use $H$.

Answer by Joseph O'Rourke for Finding points inside innermost convex hull

2010-12-31T16:56:57Z

Here is an illustration of Gerry Myerson's nice idea:

The left set has onion depth $n/3$, the right set, after small rotations, has depth 1.

Incidentally, there is an efficient algorithm to find the onion depth of a point set: $O( n \log n )$ for a set of $n$ points, established by Bernard Chazelle in the paper, "On the convex layers of a planar set," IEEE Transactions on Information Theory, 31: 509-517, 1985.

There also has been some work on the combinatorial structure of onion layers. A crude summary is: the structure is complex and not well understood. See "Onion polygonizations," Information Processing Letters Volume 57, Issue 3, 12 February 1996, Pages 165-173.

Answer by Bill Thurston for Finding points inside innermost convex hull

2010-12-31T17:54:02Z

To proceed further along the lines of Gerry Myerson's comment and Joseph O'Rourke's illustration and remarks, there is no real analytic formula to produce a point inside the innermost core as a function of $n$ points, when $n \ge 4$:

If you have a triangle with 1 point inside, then the only possible solution is that point.

If there were any analytic function, then it since it picks one of the vertices in an open neighborhood, it would need to pick that point globally. But that's impossible, since the configuration can be rearranged to make a different point the innermost one.

There is not even a continuous function that produces a point in the innermost hull, at least for 5 or more points; here the idea is illustrated with 9 points, so that the peeling the onion gives a nondegenerate inner hull:

If 6 points are added to the edges of a triangle formed by 3 of the points, then an arbitrarily small perturbation makes the first peeling produce a quadrilateral as shown. The intersection of this quadrilateral with the two other analogous quadrilaterals is empty, so there can be no continuous choice near the degenerate configuraton.

For 5 points, 2 extra points can be added so that a perturbation makes one of them into the inner hull. For 6 points, it can be arranged to be not quite as degenerate, where the inner hulls become 3 line segments that have no common intersection.