What is the name for a maximal convex set of points contained in another set of points?

Question

What is the name for a maximal convex set of points contained in another set of points $X$?

Maximal in the sense of inclusion. For the desired set to be unique, $X$ can be restricted to be a simple polygon in this discussion.

I am looking for the name of the analogue to a convex hull, but one that is contained in a set, not one that contains the set.

Answer 1

Here's a picture illustrating Brian's point in the comments:

Three maximal convex subsets of a “cross” with respect to inclusion are indicated:

1. the red “horizontal bar”
2. the blue “vertical bar”
3. the “diamond” in the middle.

The red and blue sets have area $12$ while the diamond has area $8$, hence the red and blue sets are maximal both with respect to area and inclusion while the diamond is only maximal with respect to inclusion.

---

This non-uniqueness suggests that there is no name for this concept. As Jim Conant pointed out, “convex core” would be a possibility, even though it is used with a slightly different meaning in hyperbolic geometry.

Answer 2

Given a set $X$, there is not necessarily a unique convex subset of $X$ that is maximal with respect to inclusion. For example, let $$f(x) = \begin{cases} \frac13(x+4),&-4\le x\le -1\\ \\\\ 3(x+1)+1,&-1\le x\le 0\\ \\ 4-3x,&0\le x\le 1\\\\ 1-\frac13 (x-1),&1\le x\le 4\;, \end{cases}$$ and let $X$ be the region bounded by $y=f(x)$ and $y=-f(x)$.

The square whose corners are $(0,\pm \sqrt2)$ and $(\pm \sqrt2,0)$ is one maximal convex subset of $X$. The diamond whose corners are $(0,\pm 4)$ and $(\pm \frac43,0)$ is another.

Answer 3

You might be interested in two papers. The first is by by J. S. Chang and C. K. Yap: "A polynomial solution for the potato-peeling problem" (1986):

Abstract: The potato-peeling problem asks for the largest convex polygon contained inside a given simple polygon. We give an $O(n^7)$-time algorithm to this problem, answering a question of Goodman. We also give an $O(n^6)$-time algorithm if the desired polygon is maximized with respect to perimeter.

Their definition of "largest" is maximum area, or maximum perimeter. The second, more recent paper (2009), is closer to your concerns, and offers a term for their notion: "Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance," by Dorrigiv et al.

Abstract. Given a simple polygon $P$, we consider the problem of finding a convex polygon $Q$ contained in $P$ that minimizes $H(P, Q)$, where $H$ denotes the Hausdorff distance. We call such a polygon $Q$ a Hausdorff core of $P$. We describe polynomial-time approximations for both the minimization and decision versions of the Hausdorff core problem, and we provide an argument supporting the hardness of the problem.

Answer 4

In the reference provided by Mike, the proof of the equivalence between $\mathrm{Ker}(S)$ and the intersection of the inclusion-maximal convex subsets of $S$ seems to rely on the following simple argument: "Since, for all $x \in S$, $\{x\}$ is convex, there must be some inclusion-maximal convex subset $X$ of $S$ such that $x\in X$." I believe that any set $S$ (in a real vector space) is indeed covered by its inclusion-maximal convex subsets, but I cannot see that such a simple argument holds as a proof.

Try to replace convexity by some other set property, e.g. countability, and define inclusion-maximal subsets w.r.t. this property as well. By applying the simple argument, we get, since $\{x\}$ is countable, that every $x$ is in some inclusion-maximal countable subset of $S$. This is obviously wrong, since unless $S$ is itself countable, $S$ does not have any inclusion-maximal countable subsets (if $X$ is countable then also $X\cup \{y\}$ for any $y\in S\setminus X$ is).

I suspect that proving coverage by maximal subsets relies more heavily on convexity. The property that singletons are convex seems insufficient.