MathOverflow is a question and answer site for professional mathematicians. 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

Let $P$ be a polygon in the plane. An "efficient" triangulation of $P$ is one that introduces no new vertices. We require that all introduced edges be straight and inside $P$. Every polygon in the plane has at least one efficient triangulation.

Let $R$ be a regular polygon with $n$ sides and think of it as the archetypical polygon with $n$ sides. Let $F$ be a family of efficient triangulations of $R$. We call $F$ "realizable" if there is a polygon $P$ with $n$ sides and an isomorphism of $R$ to $P$ as polygons so that the family $F$ is carried exactly to the set of efficient triangulations of $P$.

Is there a reasonable characterization of realizable families?

share|cite|improve this question
I think the only obstruction is that the edges of the triangles have to be realized by straight edges in the interior between vertices. So you could just compute all of the straight edges in the interior, and take the subset of triangulations which only use edges from this set. Is this not a sufficient characterization? – Ian Agol Jan 15 '13 at 22:47
Do you have a small example of a non-realizable set? – Brendan McKay Jan 15 '13 at 23:27
Is it okay with you if $P$ is self-intersecting? In which case I'm trying to decide if this is equivalent to the question of which rank 2 matroids are positroids, as in – Allen Knutson Jan 16 '13 at 0:43
Allen: I had in mind everything embedded. Brendan: There is much I am not sure of. If vertices of the polygon are numbered in circular order from 1 to n and the edge (1,3) is not usable and the edge (2,4) is not usable, can the edge (1,4) be usable? If the answer is no, then there should be examples. Ian: the question starts with a family of abstract triangulations and then asks if there is a real life embedding representing exactly that family. I think you are starting with the embedding and asking what the family is. – Matt Brin Jan 16 '13 at 1:41
Okay, I have a (1,3), (2,4) out and (1,4) in example (see my comment of a minute or two ago), so I am less sure there are non-realizable families. I have reasons in another language for believing so and I will see if I can really make the translation. – Matt Brin Jan 16 '13 at 1:45

Your Answer


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

Browse other questions tagged or ask your own question.