MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question

closed as general reference by Denis Serre, Wadim Zudilin, Harald Hanche-Olsen, Andrés Caicedo, Qiaochu Yuan Jan 2 '11 at 14:09

This question is too basic; it can be definitively and permanently answered by a single link to a standard internet reference source designed specifically to find that type of information.If this question can be reworded to fit the rules in the help center, please edit the question.

I am lost in attempts to understand "the formula must not use $H$" (but also your problem and motivation for it). Is related to yours? – Wadim Zudilin Dec 31 '10 at 11:52
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? – Noah Stein Dec 31 '10 at 14:29
As the OP does not bother her-/himself by clarifying the problem, I vote for closing it as spam (of Onion Peeling). – Wadim Zudilin Dec 31 '10 at 15:05
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. – Gerry Myerson Dec 31 '10 at 15:56
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. – Harald Hanche-Olsen Dec 31 '10 at 16:21
up vote 9 down vote accepted

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

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.