MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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


(This is my first question on MathOverflow! :-)

Imagine you have a set of points $S = \{p_1, \ldots, p_n\}$ in $\mathbb{R}^d$, of which $t$ are "bad". I want to compute a "safe convex hull", which is defined by $$ \bigcap_{S' \subseteq S} \mathrm{Hull}(S') \mathrm{,}$$ where $S'$ is constructed from $S$ taking away $t$ points -- in other words, $|S'| = |S| - t$.

This convex hull is necessarily inside the convex hull of the good points only. That's the interpretation of the "safe convex hull".

For $n = 5$ and $t = 1$, in $\mathbb{R}^2$, this is the Pentagram Map; for any polytope and $t = 1$, this is the very central part of the interior of a star polytope.

Do you guys know any procedure that does that for arbitrary dimensions, and for $t > 1$? A reference would be fantastic.

Thanks! :-)

share|cite|improve this question
It is likely that for small t, the intersection will be empty. For some reason the "guard number" (in a 2d polygonal art gallery, the number of guards needed to see all the faces from inside) comes to mind, and is possibly relevant. An interesting combinatorial twist: Consider a diagonal d inside a polygon. Which d live in the greatest number of convex hulls of vertices of the polygon? Gerhard "Ask Me About System Design" Paseman, 2012.10.04 – Gerhard Paseman Oct 4 '12 at 17:47
Is $d$ fixed? Naively, you can take every collection of $d$ points, check if there are at most $t$ points on one side, then intersect those $n^d$ half-spaces. – Michael Biro Oct 4 '12 at 18:20
@Michael Biro: Yes, $d$ is fixed. The problem is that you can pick $d$ points that are not affine; in this case, how to divide the entire space? (thanks!) – hmendes Oct 4 '12 at 18:57
@Gerhard Paseman: I can show, using the Helly's Theorem, that if $n > t(d+1)$ this safe convex hull will always exist. (thanks too!) – hmendes Oct 4 '12 at 18:58
@Michael Biro: Let me be more clear. Suppose all the $n$ points are in a single line in $\mathbb{R}^3$. Now, every 3 points I pick will be in a single line as well. So, the procedure would not detect that I could just remove the extremal $t$ points at both ends of the line to find the safe convex hull. It seems that I need to perform likewise in every smaller dimension before doing so in dimension $d$, but I'm not sure. Since the problem seems elementary, I suppose I could find a reference somewhere (in a paper or even in a book). – hmendes Oct 4 '12 at 19:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.