A Sweepline Algorithm for Higher Order Voronoi Diagrams
作者： Maksym Zavershynskyi , Evanthia Papadopoulou
DOI: 10.1109/ISVD.2013.17
关键词:
摘要: We present an algorithm to construct order-k Voronoi diagrams with a sweepline technique. The sites can be points or line segments. has O(nk2 log n) time complexity and O(nk) space complexity.
sci-hub.se 参考文章(19)
Mark Dubowski, Cathy East Dubowski, The Big Sweep ,(2003)
Chih-Hung Liu, Evanthia Papadopoulou, D. T. Lee, An output-sensitive approach for the L 1 /L ∞ k-nearest-neighbor Voronoi diagram european symposium on algorithms. pp. 70- 81 ,(2011) , 10.1007/978-3-642-23719-5_7
Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure ACM Computing Surveys. ,vol. 23, pp. 345- 405 ,(1991) , 10.1145/116873.116880
F. Dehne, R. Klein, The big sweep : On the power of the wavefront approach to Voronoi diagrams Algorithmica. ,vol. 17, pp. 19- 32 ,(1997) , 10.1007/BF02523236
Chee K. Yap, AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments Discrete & Computational Geometry. ,vol. 2, pp. 365- 393 ,(1987) , 10.1007/BF02187890
Rolf Klein, Elmar Langetepe, Zahra Nilforoushan, Abstract Voronoi diagrams revisited Computational Geometry. ,vol. 42, pp. 885- 902 ,(2009) , 10.1016/J.COMGEO.2009.03.002
Der-Tsai Lee, Robert L Drysdale, III, Generalization of Voronoi Diagrams in the Plane SIAM Journal on Computing. ,vol. 10, pp. 73- 87 ,(1981) , 10.1137/0210006
Pankaj K. Agarwal, Micha Sharir, Davenport–Schinzel Sequences and their Geometric Applications ,(1995)
Herbert Edelsbrunner, Raimund Seidel, Voronoi diagrams and arrangements Discrete & Computational Geometry. ,vol. 1, pp. 25- 44 ,(1986) , 10.1007/BF02187681
F. Aurenhammer, R.L.S. Drysdale, H. Krasser, Farthest line segment Voronoi diagrams Information Processing Letters. ,vol. 100, pp. 220- 225 ,(2006) , 10.1016/J.IPL.2006.07.008