Convex Hull of Path Connected sets

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

---