Traversal of a quasi-planar subdivision without using mark bits
作者： E. Chavez , J. Opatrny , S. Dobrev , L. Stacho , E. Kranakis
DOI: 10.1109/IPDPS.2004.1303250
关键词: Computational geometry 、 Triangulation 、 Traverse 、 Convex polytope 、 Computer science 、 Algorithm 、 Computational complexity theory 、 Subdivision 、 Graph theory 、 Combinatorics 、 Vertex (geometry) 、 Graph traversal 、 Tree traversal
摘要: Summary form only given. The problem of traversal planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. first such algorithms were able traverse triangulated subdivisions. Later these extended vertices an arrangement a convex polytope. research progress culminated in algorithm that can any subdivision. We extend the notion subdivision quasiplanar which we allow edges cross each other. describe satisfies simple requirement. worst case running time our O(|E| log |E|), matches for
sci-hub.se 参考文章(19)
D J Peuquet, D F Marble, Technical description of the DIME System CRC Press. pp. 123- 137 ,(1990) , 10.1201/B12579-15
Jorge Urrutia, Harvinder Singh, Evangelos Kranakis, Compass routing on geometric networks. canadian conference on computational geometry. ,(1999)
David Avis, Komei Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra symposium on computational geometry. ,vol. 8, pp. 98- 104 ,(1991) , 10.1145/109648.109659
Roy Armoni, Amnon Ta-Shma, Avi Widgerson, Shiyu Zhou, An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs Journal of the ACM. ,vol. 47, pp. 294- 311 ,(2000) , 10.1145/333979.333984
Greg Barnes, Walter L. Ruzzo, Undirected s-t connectivity in polynomial time and sublinear space Computational Complexity. ,vol. 6, pp. 1- 28 ,(1996) , 10.1007/BF01202039
Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa, A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata SIAM Journal on Computing. ,vol. 28, pp. 1051- 1072 ,(1998) , 10.1137/S0097539793282947
C. M. Gold, T. D. Charters, J. Ramsden, Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain Proceedings of the 4th annual conference on Computer graphics and interactive techniques - SIGGRAPH '77. ,vol. 11, pp. 170- 175 ,(1977) , 10.1145/563858.563887
D.E. Muller, F.P. Preparata, Finding the intersection of two convex polyhedra Theoretical Computer Science. ,vol. 7, pp. 217- 236 ,(1978) , 10.1016/0304-3975(78)90051-8
Fabian Kuhn, Roger Wattenhofer, Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing mobile ad hoc networking and computing. pp. 267- 278 ,(2003) , 10.1145/778415.778447
Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger, Geometric ad-hoc routing Proceedings of the twenty-second annual symposium on Principles of distributed computing - PODC '03. pp. 63- 72 ,(2003) , 10.1145/872035.872044