{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T21:26:18Z","timestamp":1790112378862,"version":"4.0.1"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419\u2013453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.)<\/jats:p>","DOI":"10.1137\/050631008","type":"journal-article","created":{"date-parts":[[2006,10,23]],"date-time":"2006-10-23T11:30:50Z","timestamp":1161603050000},"page":"721-739","source":"Crossref","is-referenced-by-count":16,"title":["Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm"],"prefix":"10.1137","volume":"36","author":[{"given":"Herv\u00e9","family":"Br\u00f6nnimann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lutz","family":"Kettner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michel","family":"Pocchiola","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,10,16]]},"reference":[{"key":"R1","unstructured":"P. K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang,\n                      Deformable free space tiling for kinetic collision detection\n                      , in New Directions in Algorithmic and Computational Robotics, B. Donald, K. Lynch, and D. Rus, eds., A. K. Peters, Wellesley, MA, 2001, pp. 83\u201396."},{"key":"R2","unstructured":"O. Aichholzer,\n                      Counting Triangulations\u2014Olympics\n                      , available online at http:\/\/www.cis.tugraz.at\/igi\/oaich\/triangulations\/counting\/counting.html (2003)."},{"key":"R3","unstructured":"O. Aichholzer,\n                      The path of a triangulation\n                      , in Proc. 13th European Workshop on Computational Geometry, University of W\u00fcrzburg, Germany, 1997, pp. 1\u20133."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.09.003"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021231927255"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.01.002"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411368"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"O. Aichholzer, Th. Hackl, C. Huemer, F. Hurtado, H. Krasser, and B. Vogtenhuber,\n                      On the number of plane graphs\n                      , in Proc. 17th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2006, pp. 504\u2013513.","DOI":"10.1145\/1109557.1109613"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.003"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90072-3"},{"key":"R11","unstructured":"P. Angelier and M. Pocchiola,\n                      A sum of squares theorem for visibility complexes and applications\n                      , in Discrete and Computational Geometry\u2014The Goodman\u2013Pollack Festschrift, Algorithms Combin. 25, B. Aronov, S. Basu, J. Pach, and M. Sharir, eds., Springer\u2010Verlag, Berlin, 2003, pp. 79\u2013139."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.021"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00111-6"},{"key":"R15","unstructured":"A. Bj\u00f6rner, M. Las Vergnas, N. White, B. Sturmfels, and G. M. Ziegler,\n                      Oriented Matroids\n                      , Cambridge University Press, Cambridge, UK, 1993."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"H. Br\u00f6nnimann,\n                      Designing and implementing a general purpose halfedge data structure\n                      , in Proc. 5th International Workshop on Algorithm Engineering (WAE), Lecture Notes Comput. Sci. 2141, Springer, Berlin, 2001, pp. 51\u201366.","DOI":"10.1007\/3-540-44688-5_5"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf,\n                      Computational Geometry: Algorithms and Applications\n                      , 2nd ed., Springer, Berlin, 2000.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"R19","unstructured":"E. D. Demaine, J. S. B. Mitchell, and J. O\u2019Rourke, eds,\n                      Problem 40: The Number of Pointed Pseudotriangulations\n                      , available online at http:\/\/maven.smith.edu\/orourke\/TOPP\/P40. html."},{"key":"R20","unstructured":"M. Denny and C. Sohler,\n                      Encoding a triangulation as a permutation of its point set\n                      , in Proc. 9th Canadian Conference on Computataional Geometry, Kingston, Ontario, Canada, 1997, pp. 39\u201343."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0797"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/282918.282923"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90010-8"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009464"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00007-3"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00126-8"},{"key":"R28","unstructured":"L. Kettner, D. Kirkpatrick, and B. Speckmann,\n                      Tight degree bounds for pseudo\u2010triangulations of points\n                      , in Proc. 13th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, 2001, pp. 117\u2013120."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"D. Kirkpatrick and J. Snoeyink,\n                      Computing common tangents without a separating line\n                      , in Proc. 4th Workshop on Algorithms and Data Structures (WADS), Lecture Notes Comput. Sci. 955, Springer, New York, 1995, pp. 183\u2013193.","DOI":"10.1007\/3-540-60220-8_61"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"D. Kirkpatrick, J. Snoeyink, and B. Speckmann,\n                      Kinetic collision detection for simple polygons\n                      , in Proc. 16th Annual ACM Symposium on Computing Geometry, ACM, New York, 2000, pp. 322\u2013330.","DOI":"10.1145\/336154.336219"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"D. Kirkpatrick and B. Speckmann,\n                      Separation sensitive kinetic separation for convex polygons\n                      , in Proc. Japan Conference on Discrete and Computational Geometry (JCDCG 2000), Lecture Notes Comput. Sci. 2098, Springer, Berlin, 2001, pp. 244\u2013251.","DOI":"10.1007\/3-540-47738-1_21"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"D. E. Knuth,\n                      Axioms and Hulls\n                      , Lecture Notes Comput. Sci. 606, Springer, New York, 1992.","DOI":"10.1007\/3-540-55611-7"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90093-3"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Z. Li and S. Nakano,\n                      Efficient generation of plane triangulations without repetition\n                      , in Proc. 28th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes Comput. Sci. 2076, Springer, Berlin, 2001, pp. 433\u2013443.","DOI":"10.1007\/3-540-48224-5_36"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"P. McMullen,\n                      Modern developments in regular polytopes\n                      , in Polytopes: Abstract, Convex and Computational, T. Bisztriczky, P. McMullen, R. Schneider, and A. Ivi\u0107 Weiss, eds., NATO ASI Ser. 440, Kluwer Academic Publishers, Dordrecht, 1994, pp. 97\u2013124.","DOI":"10.1007\/978-94-011-0924-6_5"},{"key":"R37","first-page":"1","volume":"47","author":"Negami S.","year":"1999","journal-title":"Yokohama Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-0523","issn-type":"print"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"M. H. Overmars and J. van Leeuwen,\n                      Dynamically maintaining configurations in the plane\n                      , in Proc. 12th Annual ACM Symposium on Theory of Computing, ACM, New York, 1980, pp. 135\u2013145.","DOI":"10.1145\/800141.804661"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00016-X"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712876"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000204"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. Pocchiola and G. Vegter,\n                      On polygonal covers\n                      , in Advances in Discrete and Computational Geometry, B. Chazelle, J. Goodman, and R. Pollack, eds., Contemp. Math. 223, AMS, Providence, RI, 1999, pp. 257\u2013268.","DOI":"10.1090\/conm\/223\/03143"},{"key":"R43","unstructured":"M. Pocchiola,\n                      Horizon trees versus pseudo\u2010triangulations\n                      , in Proc. 13th European Workshop on Computational Geometry, University of W\u00fcrzburg, Germany, 1997, p. 12."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"M. Pocchiola and G. Vegter,\n                      Pseudo\u2010triangulations: Theory and applications\n                      , in Proc. 12th Annual ACM Symposium on Computational Geometry, ACM, New York, 1996, pp. 291\u2013300.","DOI":"10.1145\/237218.237398"},{"key":"R45","unstructured":"D. Randall, G. Rote, F. Santos, and J. Snoeyink,\n                      Counting triangulations and pseudo\u2010triangulations of wheels\n                      , in Proc. 13th Canadian Conference on Computational Geometry, Waterloo, Ontario, Canada, 2001, pp. 149\u2013152."},{"key":"R46","unstructured":"S. Ray and R. Seidel,\n                      A Simple and Less Slow Method for Counting Triangulations and for Related Problems\n                      , in Proc. European Workshop on Computational Geometry, Seville University, Spain, 2004, pp. 177\u2013180."},{"key":"R47","doi-asserted-by":"crossref","unstructured":"G. Rote, I. Streinu, and F. Santos,\n                      Expansive motions and the polytope of pointed pseudo\u2010triangulations\n                      , in Discrete and Computational Geometry\u2014The Goodman\u2013Pollack Festschrift, Algorithms Combin. 25, B. Aronov, S. Basu, J. Pach, and M. Sharir, eds., Springer, Berlin, 2003, pp. 699\u2013736.","DOI":"10.1007\/978-3-642-55566-4_33"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00002-5"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1988-0928904-4"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"I. Streinu,\n                      A combinatorial approach to planar non\u2010colliding robot arm motion planning\n                      , in Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos, CA, 2000, pp. 443\u2013453.","DOI":"10.1109\/SFCS.2000.892132"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1962-002-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050631008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:50Z","timestamp":1787336750000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050631008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/050631008"],"URL":"https:\/\/doi.org\/10.1137\/050631008","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}