1
$\begingroup$

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

Maximal in terms 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.

  • 1
    Alternate question: Under what conditions will the maximal (in the sense of area) convex subset **be** unique.2015-02-03

4 Answers 4

7

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

Cross

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.

  • 0
    @Mike: Thanks, I didn't see the addendum to your comment before (must have missed it by a few seconds...). That's one reason I like answering things way outside of my field of expertise, almost every time I learn something new and interesting. That proof is really nice!2011-10-21
4

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.

  • 0
    A version of the first paper you link to is also freely available on [openlibrary.org](http://openlibrary.org/books/OL17979444M/).2011-10-21
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.

1

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.