An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments

Computational Geometry - Tập 52 - Trang 34-43 - 2016
Sang Won Bae1
1Department of Computer Science, Kyonggi University, Suwon, Republic of Korea

Tài liệu tham khảo

Alt, 2005, The Voronoi diagram of curved objects, Discrete Comput. Geom., 34, 439, 10.1007/s00454-005-1192-0

Aurenhammer, 2000, Voronoi diagrams

Bae, 2014, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Comput. Geom. Theory Appl., 47, 779, 10.1016/j.comgeo.2014.04.005

Bae, 2015, An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments, vol. 8973, 125

Chang, 2015, Detecting weakly simple polygons, 1655

Chazelle, 1991, Triangulating a simple polygon in linear time, Discrete Comput. Geom., 6, 485, 10.1007/BF02574703

Chazelle, 1992, An optimal algorithm for intersecting line segments in the plane, J. ACM, 39, 1, 10.1145/147508.147511

Cheong, 2011, Farthest-polygon Voronoi diagrams, Comput. Geom. Theory Appl., 44, 234, 10.1016/j.comgeo.2010.11.004

Chin, 1999, Finding the medial axis of a simple polygon in linear time, Discrete Comput. Geom., 21, 405, 10.1007/PL00009429

Fortune, 1987, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2, 153, 10.1007/BF01840357

Held, 1991, On the Computational Geometry of Pocket Machining, vol. 500

Karavelas, 2004, A robust and efficient implementation for the segment Voronoi diagram, 51

Kirkpatrick, 1983, Optimal search in planar subdivisions, SIAM J. Comput., 12, 28, 10.1137/0212002

Kirkpatrick, 1979, Efficient computation of continuous skeleton, 18

Klein, 1989, Concrete and Abstract Voronoi Diagrams, vol. 400

Klein, 1993, Randomized incremental construction of abstract Voronoi diagrams, Comput. Geom. Theory Appl., 3, 157, 10.1016/0925-7721(93)90033-3

Lee, 1982, Medial axis transformation of a planar shape, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4, 363, 10.1109/TPAMI.1982.4767267

Okabe, 2000

Sharir, 1995

Srinivasan, 1987, Voronoi diagram for multiply-connected polygonal domains I: algorithm, IBM J. Res. Dev., 31, 361, 10.1147/rd.313.0361

Yap, 1987, An O(nlog⁡n) algorithm for the Voronoi diagram of a set of simple curve segments, Discrete Comput. Geom., 2, 365, 10.1007/BF02187890

Thông tin
Thông tin xuất bản

Computational Geometry

Tập 52

34-43

Thông tin tác giả