Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have a convex $n$-gon, and a convex $m$-gon, in the plane. Take the convex hull of the $n+m$ vertices. How many combinatorially distinct hulls can be obtained, where two hulls are combinatorially distinct if, with the vertices labeled $a_i$, $i=1,\ldots,n$ and $b_j$, $j=1,\ldots,m$, any two cyclicly distinct strings of labels are considered distinct? Below the hulls are $(a_1,b_1,a_2,b_2,a_3,b_3)$ and $(a_1,a_2,b_2,b_3)$.
     Two Hulls
I realize this is elementary...

share|cite|improve this question
Elementary statement $\not\to$ elementary solution. Suggestion: for small values of $m$ it might not be so hard to compute the answer for $n=1,2,3\dots$. Maybe there will be a pattern, or maybe there will be something in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Feb 3 '12 at 23:35
@Gerry: Great suggestion to compute and compare to OEIS!! – Joseph O'Rourke Feb 4 '12 at 0:56

I can do the case $m=1$ (assuming I understand the problem correctly).

Take $n\ge3$. Draw your convex $n$-gon, extend all the sides to infinity. The number of distinct hulls is the number of regions into which these lines divide the plane. If no two sides are parallel, this is $1+(n^2+n)/2$, which is maximal. For two points in the same region determine the same convex hull, and two points in different regions determine different hulls.

For $n=2$, the formula gives $2$, which is right if you distinguish between $(a_1,b_1,b_2)$ and $(a_1,b_2,b_1)$, which in this case is only the distinction between clockwise and counterclockwise.

share|cite|improve this answer
Hey, that's very nice! And much more complicated than I imagined. The arrangement of lines determined by the polygon edges seems to be the key structure. Thanks for this insigh! – Joseph O'Rourke Feb 5 '12 at 20:22

Your Answer


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.