摘要: A closed curve in the plane is weakly simple if it limit (in Frechet metric) of a sequence curves. We describe an algorithm to determine whether walk length n graph O(n log n) time, improving earlier O(n3)-time Cortese et al. [Discrete Math. 2009]. As immediate corollary, we obtain first efficient arbitrary n-vertex polygon simple; our runs O(n2 time. also algorithms that detect weak simplicity time for two interesting classes polygons. Finally, discuss subtle errors several previously published definitions simplicity.
acm.org
core.ac.uk
sci-hub.st 参考文章(50)
Bruce L. Reinhart, Algorithms for Jordan Curves on Compact Surfaces The Annals of Mathematics. ,vol. 75, pp. 209- ,(1962) , 10.2307/1970169
Erin W. Chambers, Jeff Erickson, Amir Nayyeri, Minimum cuts and shortest homologous cycles Proceedings of the 25th annual symposium on Computational geometry - SCG '09. pp. 377- 385 ,(2009) , 10.1145/1542362.1542426
Leonidas J. Guibas, David Hsu, Li Zhang, A hierarchical method for real-time distance computation among moving convex bodies Computational Geometry: Theory and Applications. ,vol. 15, pp. 51- 68 ,(2000) , 10.1016/S0925-7721(99)00042-5
Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher, Perouz Taslakian, Competitive Online Routing on Delaunay Triangulations scandinavian workshop on algorithm theory. pp. 98- 109 ,(2014) , 10.1007/978-3-319-08404-6_9
Bernard Chazelle, Triangulating a simple polygon in linear time Discrete & Computational Geometry. ,vol. 6, pp. 485- 524 ,(1991) , 10.1007/BF02574703
YOSHIYUKI KUSAKARI, HITOSHI SUZUKI, TAKAO NISHIZEKI, A SHORTEST PAIR OF PATHS ON THE PLANE WITH OBSTACLES AND CROSSING AREAS International Journal of Computational Geometry and Applications. ,vol. 09, pp. 151- 170 ,(1999) , 10.1142/S021819599900011X
Prosenjit Bose, Pat Morin, Competitive online routing in geometric graphs Theoretical Computer Science. ,vol. 324, pp. 273- 288 ,(2004) , 10.1016/J.TCS.2004.05.019
John M. Boyer, Wendy J. Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition Journal of Graph Algorithms and Applications. ,vol. 8, pp. 241- 273 ,(2004) , 10.7155/JGAA.00091
Jim Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation symposium on discrete algorithms. pp. 83- 92 ,(1993) , 10.5555/313559.313615
Michael Hoffmann, Bettina Speckmann, Csaba D. Tóth, Pointed Binary Encompassing Trees Algorithm Theory - SWAT 2004. pp. 442- 454 ,(2004) , 10.1007/978-3-540-27810-8_38