응용문제에서 보로노이 다이어그램과 파워 다이어그램의 사용성 비교
Using Voronoi Diagram and Power Diagram in Application Problems
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The Voronoi diagram of spheres and power diagram have been known as powerful tools to analyze spatial characteristics of weighted points, and these structures have variety range of applications including molecular spatial structure analysis, location based optimization, architectural design, etc. Due to the fact that both diagrams are based on different distance metrics, one has better usability than another depending on application problems. In this paper, we compare these diagrams in various situations from the user’s viewpoint, and show the Voronoi diagram of spheres is more effective in the problems based on the Euclidean distance metric such as nearest neighbor search, path bottleneck locating, and internal void finding.
Abstract
The Voronoi diagram of spheres and power diagram have been known as powerful tools to analyze spatial characteristics of weighted points, and these structures have variety range of applications including molecular spatial structure analysis, location based optimization, architectural design, etc. Due to the fact that both diagrams are based on different distance metrics, one has better usability than another depending on application problems. In this paper, we compare these diagrams in various situations from the user’s viewpoint, and show the Voronoi diagram of spheres is more effective in the problems based on the Euclidean distance metric such as nearest neighbor search, path bottleneck locating, and internal void finding.
참고문헌 (21)
- Aurenhammer, F., "Power diagrams: Properties, algorithms and applications", SIAM Journal on Computing, 16, pp.78~96 (1987)
- Aurenhammer, F., "Voronoi diagrams-a survey of a fundamental geometric data structure", ACM Computing Surveys, 23(3), pp.345~405 (1991)
- Boissonnat, J.-D., "Algorithmic Geometry" (1998), Cambridge University Press
- Cho, Y., "BetaMol : A molecular modeling, analysis and visualization software based on the beta-complex and the quasi-triangulation. Journal of Advanced Mechanical Design", Systems, and Manufacturing, 6(3), pp.389~403 (2012)
- Weighted alpha shapes, "Edelsbrunner, H.", Department of Computer Science, University of Illinois at Urbana-Champaign, ~, pp.Technical Report UIUCDCS-R-92-1760 (1992)
- Edelsbrunner, H., "The union of balls and its dual shape", Discrete and Computational Geometry, 13, pp.415~440 (1995)
- Edelsbrunner, H., "The weighted volume derivative of a space-filling diagram", Proceedings of the National Academy of Science, 100(5), pp.2203~2208 (2003)
- Edelsbrunner, H., "Three-dimensional alpha shapes", ACM Transactions on Graphics, 13(1), pp.43~72 (1994)
- Goede, A., "Voronoi cell : New method for allocation of space among atoms : Elimination of avoidable errors in calculation of atomic volume", Journal of Computational Chemistry, 18(9), pp.1113~1123 (1977)
- Kim, D., "Region-expansion for the Voronoi diagram of 3D spheres", Computer-Aided Design, 38(5), pp.417~430 (2006)
- Kim, D.-S., "Euclidean Voronoi diagram of 3D balls and its computation via tracing edges", Computer-Aided Design, 37(13), pp.1412~1424
- Kim, D.-S., "Anomalies in quasi-triangulations and beta-complexes of spherical atoms in molecul", Computer-Aided Design, 45(1), pp.35~52
- 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 : II. geometry", Computer Aided Geometric Design, 18, pp.563~585 (2001)
- Kim, D.-S., "Beta-decomposition for the volume and area of the union of threedimensional balls and their offsets", Journal of Computational Chemistry, 12(3), pp.1225~1283 (2012)
- 권용주, "차량경로문제에 관한 보로노이 다이어그램 기반 타부서치 알고리듬", 대한산업공학회지, 33(4), pp.469~479 (2007), 대한산업공학회
- Okabe, A., "Spatial Tessellations : Concepts and Applications of Voronoi Diagrams. 2nd edition" (1999), John Wiley and Sons
- 박종진, "3차원 보로노이 다이어그램을 활용한 건축 디자인 생성 프로세스에 관한 연구", 한국CAD, 2009, pp.14(5), 306~313[DOI]
- Poupon, A., "Voronoi and Voronoi-related tessellations in studies of protein structure and interaction", Current Opinion in Structural Biology, 14, pp.233~241 (2004)
- Seo, J.-Y., "Regrouping service sites : A genetic approach using a Voronoi diagram", Proceedings of the Internal Conference on Computational Science and Its Applications, volume 3483 of Lecture Notes in Computer Science, pp.652~661 (2005)
- Shamos, M.I., "Closest-point problems", Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, pp.151~162 (1975)