{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:25:04Z","timestamp":1760369104580},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,8,2]],"date-time":"2012-08-02T00:00:00Z","timestamp":1343865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00454-012-9447-z","type":"journal-article","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T13:10:28Z","timestamp":1343826628000},"page":"518-579","source":"Crossref","is-referenced-by-count":3,"title":["Computing Pseudotriangulations via Branched Coverings"],"prefix":"10.1007","volume":"48","author":[{"given":"Luc","family":"Habert","sequence":"first","affiliation":[]},{"given":"Michel","family":"Pocchiola","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,8,2]]},"reference":[{"key":"9447_CR1","unstructured":"Angelier, P.: Algorithmique des graphes de visibilit\u00e9. PhD thesis, Ecole Normale Sup\u00e9rieure (Paris), February (2002)"},{"key":"9447_CR2","unstructured":"Angelier, P., Pocchiola, M.: Cgal-based implementation of visibility complexes. Technical report ECG-TR-241207-01, Effective Computational Geometry for Curves and Surfaces (ECG) (2003)"},{"key":"9447_CR3","series-title":"Algorithms and Combinatorics","first-page":"79","volume-title":"Discrete and Computational Geometry\u2014The Goodman-Pollack Festschrift, A Preliminary Version Appeared in the Proceedings of the 17th Annu. ACM Sympos. Comput. Geom. (SCG\u201901)","author":"P. Angelier","year":"2003","unstructured":"Angelier, P., Pocchiola, M.: A sum of squares theorem for visibility complexes and applications. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry\u2014The Goodman-Pollack Festschrift, A Preliminary Version Appeared in the Proceedings of the 17th Annu. ACM Sympos. Comput. Geom. (SCG\u201901). Algorithms and Combinatorics, vol. 25, pp. 79\u2013139. Springer, Berlin (2003)"},{"key":"9447_CR4","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1016\/B978-044482537-7\/50020-6","volume-title":"Handbook of Computational Geometry","author":"T. Asano","year":"2000","unstructured":"Asano, T., Ghosh, S.K., Shermer, T.C.: Visibility in the plane. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 829\u2013876. Elsevier, Amsterdam (2000)"},{"key":"9447_CR5","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF01759058","volume":"6","author":"C. Bajaj","year":"1991","unstructured":"Bajaj, C., Kim, M.S.: Convex hull of objects bounded by algebraic curves. Algorithmica 6, 533\u2013553 (1991)","journal-title":"Algorithmica"},{"key":"9447_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511586507","volume-title":"Oriented Matroids","author":"A. Bj\u00f6rner","year":"1999","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, 2nd edn. Cambridge University Press, Cambridge (1999)","edition":"2"},{"key":"9447_CR7","volume-title":"Computational Oriented Matroids","author":"J. Bokowski","year":"2006","unstructured":"Bokowski, J.: Computational Oriented Matroids. Cambridge University Press, Cambridge (2006)"},{"issue":"3","key":"9447_CR8","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/050631008","volume":"36","author":"H. Br\u00f6nnimann","year":"2006","unstructured":"Br\u00f6nnimann, H., Kettner, L., Pocchiola, M., Snoeyink, J.: Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. SIAM J. Comput. 36(3), 721\u2013739 (2006). A preliminary version appeared in the Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments (2005), pp.\u00a098\u2013110 (ALENEX\u201905)","journal-title":"SIAM J. Comput."},{"key":"9447_CR9","volume-title":"The geometry of geodesics","author":"H. Busemann","year":"1955","unstructured":"Busemann, H.: The geometry of geodesics. Academic Press, San Diego (1955)"},{"key":"9447_CR10","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"T.M. Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361\u2013368 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9447_CR11","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0012-365X(74)90080-6","volume":"9","author":"N.G. De Bruijn","year":"1974","unstructured":"De Bruijn, N.G.: Sorting by means of swappings. Discrete Math. 9(4), 333\u2013339 (1974)","journal-title":"Discrete Math."},{"key":"9447_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511530067","volume-title":"Geometry and Topology for Mesh Generation","author":"E. Edelsbrunner","year":"2001","unstructured":"Edelsbrunner, E.: Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"9447_CR13","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H. Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165\u2013194 (1989). Corrigendum in 42, 249\u2013251 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9447_CR14","first-page":"392","volume-title":"Proc. 4th Annu. ACM Sympos. Comput. Geom","author":"S. Gao","year":"1988","unstructured":"Gao, S., Jerrum, M., Kaufmann, M., Mehlhorn, K., R\u00fclling, W., Storb, C.: On continuous homotopic one layer routing. In: Proc. 4th Annu. ACM Sympos. Comput. Geom, pp. 392\u2013402 (1988)"},{"key":"9447_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543340","volume-title":"Visibility Algorithms in the Plane","author":"S.K. Ghosh","year":"2007","unstructured":"Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)"},{"key":"9447_CR16","volume-title":"El\u00e9ments de Topologie Alg\u00e9brique","author":"C. Godbillon","year":"1971","unstructured":"Godbillon, C.: El\u00e9ments de Topologie Alg\u00e9brique. Hermann, Paris (1971)"},{"issue":"9","key":"9447_CR17","doi-asserted-by":"crossref","first-page":"866","DOI":"10.2307\/2975135","volume":"101","author":"J.E. Goodman","year":"1994","unstructured":"Goodman, J.E., Pollack, R., Wenger, R., Zamfirescu, T.: Arrangements and topological planes. Am. Math. Mon. 101(9), 866\u2013878 (1994)","journal-title":"Am. Math. Mon."},{"key":"9447_CR18","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R.L. Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132\u2013133 (1972)","journal-title":"Inf. Process. Lett."},{"key":"9447_CR19","unstructured":"Habert, L., Pocchiola, M.: On chirotopes of finite planar families of pairwise disjoint convex bodies. arXiv:1101.1022v2 [math.CO]"},{"key":"9447_CR20","first-page":"314","volume-title":"Proc. 25th Ann. ACM Sympos. Comput. Geom., June 2009","author":"L. Habert","year":"2009","unstructured":"Habert, L., Pocchiola, M.: Arrangements of double pseudolines. In: Proc. 25th Ann. ACM Sympos. Comput. Geom., June 2009, pp. 314\u2013323 (2009)"},{"key":"9447_CR21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J. Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl. 4, 63\u201398 (1994)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9447_CR22","series-title":"The Raymond W. Brink Selected Mathematical Papers","first-page":"79","volume-title":"Selected Papers on Geometry","author":"R.C. James","year":"1979","unstructured":"James, R.C.: Combinatorial topology of surfaces. In: Stehney, A.K., Milnor, T.K., D\u2019Atri, J.E., Banchoff, T.F. (eds.) Selected Papers on Geometry. The Raymond W. Brink Selected Mathematical Papers, vol. 4, pp. 79\u2013114. Math. Assoc. Am., Washington (1979). Reprint from Mathematics Magazine, vol. 20 (1955), pp. 1\u201339."},{"key":"9447_CR23","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D.G. Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287\u2013299 (1986)","journal-title":"SIAM J. Comput."},{"key":"9447_CR24","series-title":"Computer Science and Information Processing","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"D. Knuth","year":"1973","unstructured":"Knuth, D.: The Art of Computer Programming: Sorting and Searching. Computer Science and Information Processing, vol.\u00a03. Addison-Wesley, Reading (1973)"},{"key":"9447_CR25","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55611-7","volume-title":"Axioms and Hulls","author":"D.E. Knuth","year":"1992","unstructured":"Knuth, D.E.: Axioms and Hulls. Lecture Notes Comput. Sci., vol.\u00a0606. Springer, Heidelberg (1992)"},{"key":"9447_CR26","series-title":"Encyclopaedia of Mathematical Sciences","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-38361-1","volume-title":"Graphs on surfaces and their applications","author":"S.K. Lando","year":"2004","unstructured":"Lando, S.K., Zvonkin, A.K.: Graphs on surfaces and their applications. Encyclopaedia of Mathematical Sciences, vol.\u00a0141. Springer, Berlin (2004)"},{"key":"9447_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-9063-4","volume-title":"A Basic Course in Algebraic Topology","author":"W.S. Massey","year":"1991","unstructured":"Massey, W.S.: A Basic Course in Algebraic Topology. Springer, Berlin (1991)"},{"key":"9447_CR28","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/B978-044482537-7\/50016-4","volume-title":"Handbook of Computational Geometry","author":"J.S.B. Mitchell","year":"2000","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633\u2013701. Elsevier, Amsterdam (2000)"},{"key":"9447_CR29","first-page":"607","volume-title":"Handbook of Discrete and Computational Geometry","author":"J.S.B. Mitchell","year":"2004","unstructured":"Mitchell, J.S.B.: Shortest paths and networks. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 607\u2013641. Chapman & Hall, Boca Raton (2004). Chap. 27"},{"issue":"1","key":"9447_CR30","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1142\/S0218195998000047","volume":"8","author":"F. Nielsen","year":"1998","unstructured":"Nielsen, F., Yvinec, M.: Output-sensitive convex hull algorithms of planar convex objects. Int. J. Comput. Geom. Appl. 8(1), 39\u201366 (1998)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9447_CR31","first-page":"643","volume-title":"Handbook of Discrete and Computational Geometry","author":"J. O\u2019Rourke","year":"2004","unstructured":"O\u2019Rourke, J.: Visibility. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 643\u2013663. Chapman & Hall, Boca Raton (2004). Chap. 28"},{"issue":"1","key":"9447_CR32","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/s00454-012-9408-6","volume":"48","author":"V. Pilaud","year":"2012","unstructured":"Pilaud, V., Pocchiola, M.: Multitriangulations, pseudotriangulations and primitive sorting networks. Discrete Comput. Geom. 48(1), 142\u2013191 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9447_CR33","first-page":"12","volume-title":"Abstracts 13th European Workshop Comput. Geom.","author":"M. Pocchiola","year":"1997","unstructured":"Pocchiola, M.: Horizon trees versus pseudo-triangulations. In: Abstracts 13th European Workshop Comput. Geom., Universit\u00e4t W\u00fcrzburg, p. 12 (1997)"},{"key":"9447_CR34","unstructured":"Pocchiola, M., Vegter, G.: Order types and visibility types of configurations of disjoint convex plane sets (extended abstract). Technical Report 94-4, Labo. Inf. Ens, 45 rue d\u2019Ulm 75230 Paris, France, January (1994)"},{"key":"9447_CR35","first-page":"291","volume-title":"Proc. 12th Annu. ACM Sympos. Comput. Geom.","author":"M. Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: Pseudo-triangulations: theory and applications. In: Proc. 12th Annu. ACM Sympos. Comput. Geom., May 1996, pp. 291\u2013300 (1996)"},{"issue":"4","key":"9447_CR36","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/BF02712876","volume":"16","author":"M. Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudotriangulations. Discrete Comput. Geom. 16(4), 419\u2013453 (1996). Special issue devoted to the proceedings of the 11th Annu. ACM Sympos. Comput. Geom. (SCG\u201995)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9447_CR37","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1142\/S0218195996000204","volume":"6","author":"M. Pocchiola","year":"1996","unstructured":"Pocchiola, M., Vegter, G.: The visibility complex. Int. J. Comput. Geom. Appl. 6(3), 279\u2013308 (1996). Special issue devoted to the proceedings of the 9th Annu. ACM Sympos. Comput. Geom. (SCG\u201993)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9447_CR38","series-title":"Encyclopedia of Mathematics and its applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511549656","volume-title":"Geometries on Surfaces","author":"B. Polster","year":"2001","unstructured":"Polster, B., Steinke, G.: Geometries on Surfaces. Encyclopedia of Mathematics and its applications, vol.\u00a084. Cambridge University Press, Cambridge (2001)"},{"issue":"3","key":"9447_CR39","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0925-7721(92)90015-K","volume":"1","author":"D. Rappaport","year":"1992","unstructured":"Rappaport, D.: A convex hull algorithm for discs, and applications. Comput. Geom. Theory Appl. 1(3), 171\u2013181 (1992)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9447_CR40","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/978-3-642-55566-4_33","volume-title":"Discrete and Computational Geometry\u2014The Goodman\u2013Pollack Festschrift","author":"G. Rote","year":"2003","unstructured":"Rote, G., Santos, F., Streinu, I.: Expansive motions and the polytope of pointed pseudo-triangulations. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry\u2014The Goodman\u2013Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 699\u2013736. Springer, Berlin (2003)"},{"key":"9447_CR41","series-title":"De Gruyter Expositions in Mathematics","doi-asserted-by":"crossref","DOI":"10.1515\/9783110876833","volume-title":"Compact Projective Planes","author":"H. Salzmann","year":"1995","unstructured":"Salzmann, H., Betten, D., Grundh\u00f6fer, T., H\u00e4hl, H., L\u00f6wen, R., Stroppel, M.: Compact Projective Planes. De Gruyter Expositions in Mathematics, vol.\u00a021. (1995). Walter de Gruyter"},{"key":"9447_CR42","unstructured":"Seidel, R.: Constrained Delaunay triangulations and Voronoi diagrams with obstacles. Technical report 260, IIG-TU Graz, Austria, 1988"},{"key":"9447_CR43","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)"},{"key":"9447_CR44","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, vol.\u00a044. Society for Industrial and Applied Mathematics, Philadelphia (1983)"},{"key":"9447_CR45","series-title":"Student Mathematical Library","doi-asserted-by":"crossref","DOI":"10.1090\/stml\/033","volume-title":"Lectures in Geometric Combinatorics","author":"R.R. Thomas","year":"2006","unstructured":"Thomas, R.R.: Lectures in Geometric Combinatorics. Student Mathematical Library, vol.\u00a033. American Mathematical Society & Institude for Advanced Study, Philadelphia (2006)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9447-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-012-9447-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-012-9447-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T11:02:00Z","timestamp":1562065320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9447-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,2]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9447"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9447-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,2]]}}}