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$.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ I am lost in attempts to understand "the formula must not use $H$" (but also your problem and motivation for it). Is mathoverflow.net/questions/22777 related to yours? $\endgroup$– Wadim ZudilinCommented Dec 31, 2010 at 11:52
-
$\begingroup$ I've tried to make the tags slightly more relevant, though I cannot understand the question either. Can you be more precise or at least give an example? $\endgroup$– Noah SteinCommented Dec 31, 2010 at 14:29
-
1$\begingroup$ As the OP does not bother her-/himself by clarifying the problem, I vote for closing it as spam (of Onion Peeling). $\endgroup$– Wadim ZudilinCommented Dec 31, 2010 at 15:05
-
3$\begingroup$ Can one find a set of points such that small perturbations cause large changes in the innermost convex hull? If so, that would suggest the difficulty of finding an analytical formula. $\endgroup$– Gerry MyersonCommented Dec 31, 2010 at 15:56
-
3$\begingroup$ Voting to close as not a real question. It is not phrased as a question, but as an imperative (“define an analytical formula”) as if it were a problem assignment, not a question coming up in research. $\endgroup$– Harald Hanche-OlsenCommented Dec 31, 2010 at 16:21
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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:
alt text http://dl.dropbox.com/u/5390048/OnionPeels.png
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.
answered Dec 31, 2010 at 17:54
$\begingroup$
$\endgroup$
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; doi:10.1109/TIT.1985.1057060, Semantic Scholar.
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, doi:10.1016/0020-0190(95)00193-X.
answered Dec 31, 2010 at 16:56