The Zigzag Path of a Pseudo-Triangulation
作者： Oswin Aichholzer , Günter Rote , Bettina Speckmann , Ileana Streinu
DOI: 10.1007/978-3-540-45078-8_33
关键词: Line (geometry) 、 Path (graph theory) 、 Type (model theory) 、 Space (mathematics) 、 Combinatorics 、 Mathematics 、 Triangulation (social science) 、 Pitteway triangulation 、 Point set triangulation 、 Zigzag
摘要: We define the zigzag path of a pseudo-triangulation, concept generalizing triangulation point set. The pseudo-triangulation allows us to use divide-and-conquer type approaches for suitable (i.e., decomposable) problems on pseudo-triangulations. For this we provide an algorithm that enumerates all paths (of pseudo-triangulations given set with respect line) in O(n 2) time per and space, where n is number points. illustrate applications our scheme which include novel count
core.ac.uk
springer.com
elsevier.com
narcis.nl参考文章(18)
Sergei Bespamyatnikh, Enumerating pseudo-triangulations in the plane. canadian conference on computational geometry. pp. 162- 166 ,(2002)
Günter Rote, Francisco Santos, Ileana Streinu, Expansive Motions and the Polytope of Pointed Pseudo-Triangulations Algorithms and Combinatorics. pp. 699- 736 ,(2003) , 10.1007/978-3-642-55566-4_33
Adrian Dumitrescu, Bernd Gärtner, Samuele Pedroni, Emo Welzl, Enumerating triangulation paths Computational Geometry: Theory and Applications. ,vol. 20, pp. 3- 12 ,(2001) , 10.1016/S0925-7721(01)00031-1
Sergey Bereg, Enumerating pseudo-triangulations in the plane Computational Geometry: Theory and Applications. ,vol. 30, pp. 207- 222 ,(2005) , 10.1016/J.COMGEO.2004.09.002
B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, J. Snoeyink, Ray shooting in polygons using geodesic triangulations Algorithmica. ,vol. 12, pp. 54- 68 ,(1994) , 10.1007/BF01377183
David Avis, Komei Fukuda, Reverse search for enumeration Discrete Applied Mathematics. ,vol. 65, pp. 21- 46 ,(1996) , 10.1016/0166-218X(95)00026-N
David Avis, Computational experience with the reverse search vertex enumeration algorithm Optimization Methods & Software. ,vol. 10, pp. 107- 124 ,(1998) , 10.1080/10556789808805706
Oswin Aichholzer, The path of a triangulation symposium on computational geometry. pp. 14- 23 ,(1999) , 10.1145/304893.304896
Michael T Goodrich, Roberto Tamassia, Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations Journal of Algorithms. ,vol. 23, pp. 51- 73 ,(1997) , 10.1006/JAGM.1995.0797
Sergei Bespamyatnikh, An efficient algorithm for enumeration of triangulations Computational Geometry: Theory and Applications. ,vol. 23, pp. 271- 279 ,(2002) , 10.1016/S0925-7721(02)00111-6