OP-01086 Open

Pointed pseudotriangulations versus triangulations

Let $S$ be a finite set of points in the plane. A pseudotriangle is a simple polygon with exactly three convex vertices; between any two of them its boundary is a reflex chain, possibly a single segment, so every triangle is a pseudotriangle. A pseudotriangulation of $S$ subdivides the convex hull of $S$ into pseudotriangles whose vertices are exactly the points of $S$. It is called pointed (or minimum) if it has the fewest edges among all pseudotriangulations of $S$.

Brönnimann, Kettner, Pocchiola and Snoeyink checked the question below for all sets of at most $9$ points, and Aichholzer reported the case of $10$ points. Aichholzer, Aurenhammer, Krasser and Speckmann proved that, over all sets of $n$ points, the number of pointed pseudotriangulations is smallest for points in convex position.

Problem. Does every finite planar point set $S$ have at least as many pointed pseudotriangulations as triangulations?

Source: Randall, Rote, Santos and Snoeyink (2001); posed by Snoeyink at the CCCG 2001 open-problem session; Problem 40 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary: CO — Combinatorics
Secondary: MG
Keywords: counting triangulations, pseudotriangulations, The Open Problems Project

References

@inproceedings{randall2001,
  author    = {Randall, D. and Rote, G. and Santos, F. and Snoeyink, J.},
  title     = {Counting triangulations and pseudotriangulations of wheels},
  booktitle = {Proc. 13th Canad. Conf. Comput. Geom.},
  year      = {2001},
  pages     = {149--152}
}

@unpublished{bronnimann2001,
  author = {Br{\"o}nnimann, H. and Kettner, L. and Pocchiola, M. and Snoeyink, J.},
  title  = {Counting and Enumerating Pseudo-triangulations with the Greedy Flip Algorithm},
  year   = {2001},
  note   = {\url{http://www.cs.unc.edu/Research/compgeom/pseudoT/}}
}

@inproceedings{aichholzer2002convexity,
  author    = {Aichholzer, Oswin and Aurenhammer, Franz and Krasser, Hannes and Speckmann, Bettina},
  title     = {Convexity Minimizes Pseudo-Triangulations},
  booktitle = {Proc. 14th Canad. Conf. Comput. Geom.},
  year      = {2002},
  pages     = {158--161}
}

@inproceedings{streinu2000,
  author    = {Streinu, Ileana},
  title     = {A combinatorial approach to planar non-colliding robot arm motion planning},
  booktitle = {Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci.},
  publisher = {IEEE},
  year      = {2000},
  pages     = {443--453}
}

@article{kettner2003,
  author  = {Kettner, Lutz and Kirkpatrick, David and Mantler, Andrea and Snoeyink, Jack and Speckmann, Bettina and Takeuchi, Fumihiko},
  title   = {Tight Degree Bounds for Pseudo-Triangulations of Points},
  journal = {Comput. Geom. Th. Appl.},
  volume  = {25},
  number  = {1--2},
  year    = {2003},
  doi     = {10.1016/S0925-7721(02)00126-8}
}

@article{orourke2002column43,
  author  = {O'Rourke, J.},
  title   = {Computational geometry column 43},
  journal = {Internat. J. Comput. Geom. Appl.},
  volume  = {12},
  number  = {3},
  year    = {2002},
  pages   = {263--265}
}

@inproceedings{demaine2002cccg2001,
  author    = {Demaine, Erik D. and O'Rourke, Joseph},
  title     = {Open Problems from {CCCG} 2001},
  booktitle = {Proceedings of the 14th Canadian Conference on Computational Geometry},
  year      = {2002},
  note      = {\url{http://www.cs.uleth.ca/~wismath/cccg/papers/open.pdf}}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01086, "Pointed pseudotriangulations versus triangulations", clopen.solutions.