Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Brian M. Scott Oct 19 '11 at 23:45
1  
I would suggest the term "convex core." –  Grumpy Parsnip Oct 20 '11 at 0:04
    
The term "maximal convex subset" appears to be used fairly widely in the literature. –  Mike Spivey Oct 20 '11 at 0:35
add comment

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
Or just take finite set. Every singleton is a maximal convex subset, so the maximal one is not unique. –  Grumpy Parsnip Oct 20 '11 at 1:41
    
By the way, @t.b., why the name change? (Just idle curiosity.) –  Grumpy Parsnip Oct 20 '11 at 1:42
    
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" –  t.b. Oct 20 '11 at 1:43
    
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. –  t.b. Oct 20 '11 at 1:47
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. –  Mike Spivey Oct 21 '11 at 15:54
show 6 more comments

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.

share|improve this answer
    
A version of the first paper you link to is also freely available on openlibrary.org. –  t.b. Oct 21 '11 at 1:06
    
Thanks, t.b.! $\mbox{}$ –  Joseph O'Rourke Oct 21 '11 at 1:41
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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