Computing Pseudotriangulations via Branched Coverings

详细信息    查看全文

• 作者：Luc Habert (1) Luc.Habert@normalesup.org
  Michel Pocchiola (1) pocchiola@math.jussieu.fr
• 关键词：Convexity – ; Convex hulls – ; Pseudotriangulations – ; Constrained pseudotriangulations – ; Partial linear spaces – ; Visibility complexes – ; Topological planes – ; Branched coverings – ; Geometric predicates – ; Chirotopes – ; Fundamental and practical algorithms
• 刊名：Discrete and Computational Geometry
• 出版年：2012
• 出版时间：October 2012
• 年：2012
• 卷：48
• 期：3
• 页码：518-579
• 全文大小：2.0 MB
• 参考文献：1. Angelier, P.: Algorithmique des graphes de visibilit茅. PhD thesis, Ecole Normale Sup茅rieure (Paris), February (2002)
  2. 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)
  3. 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—The Goodman-Pollack Festschrift, A Preliminary Version Appeared in the Proceedings of the 17th Annu. ACM Sympos. Comput. Geom. (SCG’01). Algorithms and Combinatorics, vol. 25, pp. 79–139. Springer, Berlin (2003)
  4. 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–876. Elsevier, Amsterdam (2000)
  5. Bajaj, C., Kim, M.S.: Convex hull of objects bounded by algebraic curves. Algorithmica 6, 533–553 (1991)
  6. Bj枚rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, 2nd edn. Cambridge University Press, Cambridge (1999)
  7. Bokowski, J.: Computational Oriented Matroids. Cambridge University Press, Cambridge (2006)
  8. Br枚nnimann, H., Kettner, L., Pocchiola, M., Snoeyink, J.: Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. SIAM J. Comput. 36(3), 721–739 (2006). A preliminary version appeared in the Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments (2005), pp. 98–110 (ALENEX’05)
  9. Busemann, H.: The geometry of geodesics. Academic Press, San Diego (1955)
  10. Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361–368 (1996)
  11. De Bruijn, N.G.: Sorting by means of swappings. Discrete Math. 9(4), 333–339 (1974)
  12. Edelsbrunner, E.: Geometry and Topology for Mesh Generation. Cambridge University Press, Cambridge (2001)
  13. Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165–194 (1989). Corrigendum in 42, 249–251 (1991)
  14. Gao, S., Jerrum, M., Kaufmann, M., Mehlhorn, K., R眉lling, W., Storb, C.: On continuous homotopic one layer routing. In: Proc. 4th Annu. ACM Sympos. Comput. Geom, pp. 392–402 (1988)
  15. Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)
  16. Godbillon, C.: El茅ments de Topologie Alg茅brique. Hermann, Paris (1971)
  17. Goodman, J.E., Pollack, R., Wenger, R., Zamfirescu, T.: Arrangements and topological planes. Am. Math. Mon. 101(9), 866–878 (1994)
  18. Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132–133 (1972)
  19. Habert, L., Pocchiola, M.: On chirotopes of finite planar families of pairwise disjoint convex bodies. arXiv:1101.1022v2 [math.CO]
  20. Habert, L., Pocchiola, M.: Arrangements of double pseudolines. In: Proc. 25th Ann. ACM Sympos. Comput. Geom., June 2009, pp. 314–323 (2009)
  21. Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl. 4, 63–98 (1994)
  22. James, R.C.: Combinatorial topology of surfaces. In: Stehney, A.K., Milnor, T.K., D’Atri, J.E., Banchoff, T.F. (eds.) Selected Papers on Geometry. The Raymond W. Brink Selected Mathematical Papers, vol. 4, pp. 79–114. Math. Assoc. Am., Washington (1979). Reprint from Mathematics Magazine, vol. 20 (1955), pp. 1–39.
  23. Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287–299 (1986)
  24. Knuth, D.: The Art of Computer Programming: Sorting and Searching. Computer Science and Information Processing, vol. 3. Addison-Wesley, Reading (1973)
  25. Knuth, D.E.: Axioms and Hulls. Lecture Notes Comput. Sci., vol. 606. Springer, Heidelberg (1992)
  26. Lando, S.K., Zvonkin, A.K.: Graphs on surfaces and their applications. Encyclopaedia of Mathematical Sciences, vol. 141. Springer, Berlin (2004)
  27. Massey, W.S.: A Basic Course in Algebraic Topology. Springer, Berlin (1991)
  28. Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633–701. Elsevier, Amsterdam (2000)
  29. Mitchell, J.S.B.: Shortest paths and networks. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 607–641. Chapman & Hall, Boca Raton (2004). Chap. 27
  30. Nielsen, F., Yvinec, M.: Output-sensitive convex hull algorithms of planar convex objects. Int. J. Comput. Geom. Appl. 8(1), 39–66 (1998)
  31. O’Rourke, J.: Visibility. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, pp. 643–663. Chapman & Hall, Boca Raton (2004). Chap. 28
  32. Pilaud, V., Pocchiola, M.: Multitriangulations, pseudotriangulations and primitive sorting networks. Discrete Comput. Geom. 48(1), 142–191 (2012)
  33. Pocchiola, M.: Horizon trees versus pseudo-triangulations. In: Abstracts 13th European Workshop Comput. Geom., Universit盲t W眉rzburg, p. 12 (1997)
  34. 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’Ulm 75230 Paris, France, January (1994)
  35. Pocchiola, M., Vegter, G.: Pseudo-triangulations: theory and applications. In: Proc. 12th Annu. ACM Sympos. Comput. Geom., May 1996, pp. 291–300 (1996)
  36. Pocchiola, M., Vegter, G.: Topologically sweeping visibility complexes via pseudotriangulations. Discrete Comput. Geom. 16(4), 419–453 (1996). Special issue devoted to the proceedings of the 11th Annu. ACM Sympos. Comput. Geom. (SCG’95)
  37. Pocchiola, M., Vegter, G.: The visibility complex. Int. J. Comput. Geom. Appl. 6(3), 279–308 (1996). Special issue devoted to the proceedings of the 9th Annu. ACM Sympos. Comput. Geom. (SCG’93)
  38. Polster, B., Steinke, G.: Geometries on Surfaces. Encyclopedia of Mathematics and its applications, vol. 84. Cambridge University Press, Cambridge (2001)
  39. Rappaport, D.: A convex hull algorithm for discs, and applications. Comput. Geom. Theory Appl. 1(3), 171–181 (1992)
  40. 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—The Goodman–Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 699–736. Springer, Berlin (2003)
  41. Salzmann, H., Betten, D., Grundh枚fer, T., H盲hl, H., L枚wen, R., Stroppel, M.: Compact Projective Planes. De Gruyter Expositions in Mathematics, vol. 21. (1995). Walter de Gruyter
  42. Seidel, R.: Constrained Delaunay triangulations and Voronoi diagrams with obstacles. Technical report 260, IIG-TU Graz, Austria, 1988
  43. Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York (1995)
  44. Tarjan, R.E.: Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44. Society for Industrial and Applied Mathematics, Philadelphia (1983)
  45. Thomas, R.R.: Lectures in Geometric Combinatorics. Student Mathematical Library, vol. 33. American Mathematical Society & Institude for Advanced Study, Philadelphia (2006)
• 作者单位：1. Institut de Math茅matiques de Jussieu, UMR 7586, Universit茅 Pierre & Marie Curie, 4 place Jussieu, 75252 Paris Cedex 05, France
• ISSN：1432-0444

文摘

We describe an efficient algorithm to compute a pseudotriangulation of a finite planar family of pairwise disjoint convex bodies presented by its chirotope. The design of the algorithm relies on a deepening of the theory of visibility complexes and on the extension of that theory to the setting of branched coverings. The problem of computing a pseudotriangulation that contains a given set of bitangent line segments is also examined.