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$.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
|
|||||||||||||||||||||
|
closed as spam by Denis Serre, Wadim Zudilin, Harald Hanche-Olsen, Andres Caicedo, Qiaochu Yuan Jan 2 2011 at 14:09 |
|
10
|
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. |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
5
|
Here is an illustration of Gerry Myerson's nice idea:
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. |
||
|
|
