10
$\begingroup$

This is a pretty easy question to ask, but haven't seen it anywhere.


Suppose I have some continuous path $X$ in $\mathbb{R}^n$ and I want to get the convex hull of $X$, $\operatorname{co}(X)$.

Is it enough to consider only pairwise convex combinations of points in $X$ to generate $\operatorname{co}(X)$? I.e.,

$$\left(\forall z\in \operatorname{co}\left(X\right) \right) \left(\exists\lambda \in \left[0,1\right] \land x_{0},x_{1}\in X \right) \left(z=\lambda x_{0}+(1-\lambda)x_{1} \right)$$

Also, if this is true, is it generalizable to more general topological spaces? Thanks!

$\endgroup$

4 Answers 4

21
$\begingroup$

This is true in $\mathbb R^2$ but not in higher dimensions. For example, consider a path in $\mathbb R^3$ that lies in the half-space $z\ge 0$ and touches the $xy$-plane at three non-collinear points. The convex hull contains the solid triangle spanned by these points, but pairwise convex combinations only give you three segments in that plane.

$\endgroup$
12
$\begingroup$

No, it is not enough to consider convex combinations of pairs of points in the connected set. A famous example is the moment curve $(t,t^2,t^3,\dots,t^n)$ where when you take the convex hull all convex combinations of [n/2] points form a face of the convex hull. Caratheodory theorem asserts that for every $X$ in $\mathbb{R}^n$ a point in the convex hull of X is in the convex hull of $d+1$ points from $X$. I vaguely remember that when $X$ is connected you can replace $d+1$ by $d$ but I am not sure about it.

Added later: Indeed it is an old theorem that you can replace $d+1$ with $d$ when $X$ is connected. A recent theorem of Barany and Karasev assets that if $X$ is a set in $\mathbb{R}^d$ with the property that all projections of $X$ into a $k$ dimensional space are convex, then every point in the convex hull of $X$ is already in the convex hull of $d+1-k$ points from $X$.

$\endgroup$
5
$\begingroup$

The answer is no. For example, it's fairly easy to draw a knot $S^1 \to \mathbb R^3$ such that the convex hull is not the same thing as the set of all secants. If you want a concrete example, take a standard parametrization of a trefoil, so that the origin is the intersection of two axis of symmetry. You'll see the origin is in the convex hull, but its not on the set of secants.

$\endgroup$
7
  • $\begingroup$ Dear Ryan, your answer came 13 seconds before mine. $\endgroup$
    – Gil Kalai
    Oct 6, 2011 at 18:59
  • $\begingroup$ Dear Gil: and your answer is more concrete than mine. $\endgroup$ Oct 6, 2011 at 19:19
  • $\begingroup$ all three answers are nice and rather different.. i never thought about the convex hull of the standard realization of the trefoil, looks interesting. $\endgroup$
    – Gil Kalai
    Oct 6, 2011 at 19:36
  • $\begingroup$ The geometry of the the convex hull of a smooth knot has some connections to finite-type invariants (via my work with Conant, Sinha and Scannell). It's also connected to rope-length geometry / packing type problems for knots, via work of John Sullivan, Kusner, Cantarella, Denne and that group. $\endgroup$ Oct 6, 2011 at 22:00
  • 1
    $\begingroup$ And here is the Cantarella, Kuperburg, Kusner and Sullivan reference that I was thinking of, but forgot to accurately cite: front.math.ucdavis.edu/0204.5106 $\endgroup$ Oct 9, 2011 at 16:39
3
$\begingroup$

This is just a computational footnote to the thrust of this old question, but I wanted to mention that finding the convex hull of a polygonal path is computationally easier in $\mathbb{R}^2$ that finding the hull of unconnected points: It can be computed in $O(n)$—linear time—compared to the $\Omega(n \log n)$ lower bound for unconnected points:

Melkman, Avraham A. "On-line construction of the convex hull of a simple polyline." Information Processing Letters 25, No. 1 (1987): 11-12. (ACM link.)


         
          Image from Joe Mitchell's course notes: PDF download.


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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