MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

A convex polygon $P$ having an interior point $A$ in generic position (not on any line defined by two vertices) can be encoded combinatorially by associating to every vertex $v$ of $P$ the unique edge $e(v)$ of $P$ such that $A$ is contained in the triangle defined as the convex hull of $v$ and $e(v)$. (Equivalently, $e(v)$ is the unique edge whose interior intersects the line containing the two points $v$ and $A$.)

To what extend does the converse hold: given a cyclically ordered set of $n$ abstract "vertices" $v_1,\dots,v_n$ and a function $e$ which associates to every vertex an "edge" consisting of two other cyclically consecutive vertices, does the function $e$ arise as above as the function indicating the combinatorial position of a fixed interior point for a suitable planar realization of the points $v_1,\dots,v_n$ in convex position?

A necessary condition is of course that any two "abstract" triangles intersect, ie. the intersection of two distinct "triangles" should have strictly positive area in any geometric realization of the $n$ cyclically ordered points in convex position.

Are there other restrictions? (There are none for $n\leq 5$ at least.)

Added: The combinatorial situation depicted above can be encoded as follows: One consider $n$ red beans (vertices) $r_1,\dots,r_n$ and $n$ black beans ("edges" or more precisely the intersection of a line through a vertex and the interior point $A$) $b_1,\dots,b_n$ on a circle $S$ where the indices of both read and black beans correspond to the induced cyclic order.
We require moreover that every black bean $b_i$ is separated from the read bean $r_i$ by at least one other read bean on both intervals of $S\setminus\{b_i,r_i\}$. This situation gives rise to an involution since the last condition holds then also with colors reversed. In particular, if the necessary condition above is sufficient for a given $n$, then there is also always a "dual" configuration for every convex polygon together with a generic interior point.

Second PS: Zaimi's proof shows that such configurations come indeed in pairs as the read and black bean model shows. A direct proof is as follows: Given a realization with vertices corresponding to read beans, define the black vertices (beans) by intersecting all $n$ lines through $A$ and a vertex. A small perturbation into convex position of the black vertices realizes the dual configuration.

Zaimi's proof implies that we can count (up to combinatorial orientation-preserving equivalence or up to isotopy, they coincide in this case) the number of such configuration with $n$ vertices in convex position and an additional interior point. There are $$-1+\frac{1}{2n}\sum_{d\vert n,\ d\equiv 1\pmod 2}\phi(d)2^{n/d}$$ of them with $\phi(d)$ Euler's indicator function defined by $\phi(1)=1$ and $\phi(n)$ given by the number of invertible integers modulo $n$ for $n>1$. The first non-zero terms are $1,1,3,5,9,15,29,51,93,171,\dots$ for $n=3,4,\dots$.

share|cite|improve this question
up vote 3 down vote accepted

Given $e$ so that it satisfies your condition of distinct triangles intersecting nontrivially we will prove that it comes from an associated polygon by induction on the number of vertices of the polygon.

First pick an $i$ so that our internal point is not contained in the triangle $(i-1,i,i+1)$, where indices are mod $n$. Now from the induction hypothesis there is a polygon $P_1P_2\cdots\hat{P_i}\cdots P_n$ on $n-1$ vertices and a point inside it so that the data agrees with $e$ on these vertices.

Suppose $P_{i-2}P_{i-1}\cap P_{i+1}P_{i+2}=Q_i$, so that we have to choose $P_i$ inside the triangle $\triangle P_{i-1}Q_iP_{i+1}$. The only thing we need to take care of is that the line joining $P_i$ to the internal point intersects the appropriate edge of the polygon as described by $e$ (This is also equivalent to making sure that among the vertices which are paired up with the edge $P_{i-1}P_{i+1}$ the appropriate subsets are paired with $P_{i-1}P_{i}$ or $P_{i}P_{i+1}$ after the point $P_i$ is added). Notice that the intersection condition implies that the edge prescribed to $P_i$ lies between those prescribed to $P_{i-1}$ and $P_{i+1}$. So it follows from a continuity argument that some point inside $\triangle P_{i-1}Q_iP_{i+1}$ satisfies the required condition.

share|cite|improve this answer
Nice. Thank you. – Roland Bacher Apr 3 '12 at 12:17
@Gjergji Zaimi: I believe now that your proof is not complete. It works if the internal point is on no triangle involving the edge $(i-1,i)$ or the edge $(i,i+1)$ (and a convex vertex). Indeed, removing the "point" $P_i$ enlarges this edge and makes more room for the internal point. It can thus happen that it is no longer possible to put back an appropriate point $P_i$. Remark that one can easily suppose that only one of the edges $(i\pm 1,i)$ is involved in "special" triangles but this case has to be considered carefully. – Roland Bacher Apr 5 '12 at 8:26
I added a remark that emphasises that the only condition which is needed for the inductive step is to choose $P_i$ so that $P_i$ lies in the intersection of $\triangle P_{i-1}Q_iP_{i+1}$ and the region between the rays $\vec{P_rO}$ and $\vec{P_{r+1}O}$. – Gjergji Zaimi Apr 5 '12 at 9:47
Here $O$ is the interior point and $P_rP_{r+1}$ is the edge associated to $P_i$. – Gjergji Zaimi Apr 5 '12 at 10:07
This is convincing! – Roland Bacher Apr 5 '12 at 12:08

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.