AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments
作者： Chee K. Yap
DOI: 10.1007/BF02187890
关键词:
摘要: LetX be a given set ofn circular and straight line segments in the plane where two may interest only at their endpoints. We introduce new technique that computes Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of problem. The algorithm is relatively simple, an important factor numerous practical applications diagram.
springer.com
acm.org
sci-hub.se 参考文章(24)
Robert Lewis (Scot) Drysdale, Generalized voronoi diagrams and geometric searching. Stanford University. ,(1979)
Hans P. Moravec, Robot Rover Visual Navigation ,(1981)
S. J. Fortune, A fast algorithm for polygon containment by translation international colloquium on automata, languages and programming. pp. 189- 198 ,(1985) , 10.1007/BFB0015744
Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions University of British Columbia. ,(1981) , 10.14288/1.0051821
F. P. Preparata, The medial axis of a simple polygon mathematical foundations of computer science. pp. 443- 450 ,(1977) , 10.1007/3-540-08353-7_166
Colm Ó'Dúnlaing, Chee K Yap, A Retraction Method for Planning the Motion of a Disc Journal of Algorithms. ,vol. 6, pp. 104- 111 ,(1985) , 10.1016/0196-6774(85)90021-5
Daniel Leven, Micha Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams ,(2011)
D. T. Lee, Medial Axis Transformation of a Planar Shape IEEE Transactions on Pattern Analysis and Machine Intelligence. ,vol. PAMI-4, pp. 363- 369 ,(1982) , 10.1109/TPAMI.1982.4767267
Hiroshi Imai, Masao Iri, Kazuo Murota, VORONOI DIAGRAM IN THE LAGUERRE GEOMETRY AND ITS APPLICATIONS SIAM Journal on Computing. ,vol. 14, pp. 93- 105 ,(1985) , 10.1137/0214006
L. Paul Chew, Robert L. (Scot) Dyrsdale, Voronoi diagrams based on convex distance functions symposium on computational geometry. pp. 235- 244 ,(1985) , 10.1145/323233.323264