영역 확장법을 통한 평면에서 원들의 보로노이 다이어그램의 강건한 계산
Robust Construction of Voronoi Diagram of Circles by Region-Expansion Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper presents a numerically robust algorithm to construct a Voronoi diagram of circles in the plane. The circles are allowed to have intersections among them, but one circle cannot fully contain another circle. The Voronoi diagram is a tessellation of the plane into Voronoi regions of given circles. Each circle has its Voronoi region which is defined by a set of points in the plane closer to the circle than any other circles. The distance from a point p to a circle ci of center pi and radius ri is ||p-pi||-ri, which is the closest Euclidean distance from p to the circle boundary. The proposed algorithm first constructs the point Voronoi diagram of centers of given circles, then it enlarges each point to the circle and expands its Voronoi region accordingly. This region-expansion process is done by local modifications and after completing this process for the whole circles the desired circle Voronoi diagram can be obtained. The proposed algorithm is numerically robust and we provide with a few examples to show its robustness. The algorithm runs in O(n2) time in the worst case and O(n) time on average where n is the number of the circles. The experiment shows that the region-expansion algorithm is robust and runs fast with strong linear time behavior.
Abstract
This paper presents a numerically robust algorithm to construct a Voronoi diagram of circles in the plane. The circles are allowed to have intersections among them, but one circle cannot fully contain another circle. The Voronoi diagram is a tessellation of the plane into Voronoi regions of given circles. Each circle has its Voronoi region which is defined by a set of points in the plane closer to the circle than any other circles. The distance from a point p to a circle ci of center pi and radius ri is ||p-pi||-ri, which is the closest Euclidean distance from p to the circle boundary. The proposed algorithm first constructs the point Voronoi diagram of centers of given circles, then it enlarges each point to the circle and expands its Voronoi region accordingly. This region-expansion process is done by local modifications and after completing this process for the whole circles the desired circle Voronoi diagram can be obtained. The proposed algorithm is numerically robust and we provide with a few examples to show its robustness. The algorithm runs in O(n2) time in the worst case and O(n) time on average where n is the number of the circles. The experiment shows that the region-expansion algorithm is robust and runs fast with strong linear time behavior.
참고문헌 (15)
- Cho, Y., "BetaMol : a molecular modeling, analysis and visualization software based on the betacomplex and the quasi-triangulation", Journal of Advanced Mechanical Design, Systems, and Manufacturing, 6(3), pp.389~403 (2012)
- Emiris, I. Z., "The predicates of the Apollonius diagram : Algorithmic analysis and implementation", Computational Geometry-Theory and Applications, 33, pp.18~57 (2006)
- Fortune, S., "A sweepline algorithm for Voronoi diagrams", Algorithmica, 2, pp.153~174 (1987)
- Kim, D., "Pocket extraction on proteins via the Voronoi diagram of spheres", Journal of Molecular Graphics & Modelling, 26(7), pp.1104~1112 (2008)
- Kim, D. -S, "Quasitriangulation and interworld data structure in three dimensions", Computer-Aided Design, 38(7), pp.808~819 (2006)
- Kim, D. -S., "Voronoi diagram of a circle set from Voronoi diagram of a point set : I. topology", Computer Aided Geometric Design, 18, pp.541~562 (2001)
- Kim, D. -S., "Voronoi diagram of a circle set from Voronoi diagram of a point set : Ⅱ. geometry", Computer Aided Geometric Design, 18, pp.563~585 (2001)
- Kim, D. -S., "Shortest paths for disc obstacles", Proceedings of the International Conference on Computational Science and Its Applications-ICCSA2004, Lecture Notes in Computer Science, 3045, pp.62~70 (2004)
- Kim, J. -K., "BetaVoid : molecular voids via betacomplexes and Voronoi diagrams", Proteins : Structure, Functions, and Bioinformatics, 82(9), pp.1829~1849 (2014)
- Lee, D., "Generalization of Voronoi diagrams in the plane", SIAM Journal on Computing, 10(1), pp.73~87 (1981)
- Lee, M., "Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks", ACM Transactions on Mathe matical Software, 43(2), pp.14~ (2016)[DOI]
- Sharir, M., "Intersection and closest-pair problems for a set of planar discs", SIAM Journal on Computing, 14(2), pp.448~468 (1985)
- Sugihara, K., "A robust topology-oriented incremental algorithm for Voronoi diagrams", International Journal of Computational Geometry & Applications, 4(2), pp.179~228 (1994)
- Sugihara, K., "Disk packing for the estimation of the size of a wire bundle", Japan Journal of Industrial and Applied Mathematics, 21(3), pp.259~278 (2004)
- Yap, C. -K., "An O(nlogn)algorithm for the Voronoi diagram of a set of simple curve segments", Discrete &Computational Geometry, 2, pp.365~393 (1987)