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.

  • 3
    Maximal in what sense? Inclusion? Area? In neither sense is there necessarily a unique set of that kind, so I rather doubt that such a term exists.2011-10-19
  • 1
    I would suggest the term "convex core."2011-10-20
  • 0
    The term "maximal convex subset" appears to be used fairly widely in the literature.2011-10-20
  • 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
    Or just take finite set. Every singleton is a maximal convex subset, so the maximal one is not unique.2011-10-20
  • 0
    By the way, @t.b., why the name change? (Just idle curiosity.)2011-10-20
  • 0
    Right, thanks. I thought this example was a bit more interesting :) It is also a reaction to the clarification of the question "X can be restricted to be a simple polygon"2011-10-20
  • 0
    Oh, I was trying to get the math.SE account off the first page of Google hits for my real name. I also started to receive a lot of email from users asking me for personal advice and I don't like to be impolite and not respond, but I prefer to keep my SE-activity strictly on this site and as on-topic as possible.2011-10-20
  • 0
    Agreed. Your example is more interesting. Also, that makes sense about your real name. Cheers!2011-10-20
  • 0
    Aside: The intersection of the horizontal bar, the vertical bar, and the diamond (so, the square in the middle) is called the "kernel" of the cross-shaped set.2011-10-21
  • 0
    @Mike: Thanks for pointing this out. Just to make sure I understand the concept correctly: what is the definition of the kernel? Would that be the intersection of all inclusion-maximal convex subsets? So it could be empty, as for example in an H-shaped polygon?2011-10-21
  • 1
    @t.b.: You have the idea right. The definition is as follows, though: Given $x \in S$, a point $y \in S$ is *visible* from $x$ if $\lambda x + (1-\lambda) y \in S$ for $\lambda \in [0,1]$. Let $S_x$ denote the set of all points visible from $x$. Then $Ker(S) = \cap_x S_x$. It's not hard to show that this is equivalent to $Ker(S)$ being the intersection of all inclusion-maximal convex sets.2011-10-21
  • 0
    @Mike: Thanks for the clarification. Your definition is probably more intuitive even if I'm not quite sure I understand it fully, yet. (I was a bit too quick, first). I then Googled a bit and found [this article of Lee and Preparata](http://asignatura.us.es/fgcitig/Articulos/03-An%20optimal%20algorithm%20for%20finding%20the%20kernel%20of%20a%20polygon.pdf) that calculates the kernel of a simple polygon with $n$ vertices in $O(n)$ time. That's rather surprising to me, but very nice.2011-10-21
  • 0
    @t.b.: Interesting. Thanks for the reference. And [here's a reference](http://books.google.com/books?id=YquhYYBJh5sC&pg=PA35&dq=kernel+%22maximal+convex+subset%22&hl=en&ei=F5-hTpyYJcLciAKPzKyIAQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC4Q6AEwAA#v=onepage&q=kernel%20%22maximal%20convex%20subset%22&f=false) for the equivalence to $Ker(s)$ being the intersection of the inclusion-maximal convex subsets.2011-10-21
  • 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.