Approximations of 2D and 3D generalized Voronoi diagrams. (English) Zbl 1145.65008
Summary: We propose a new approach for computing in an efficient way polygonal approximations of generalized 2D/3D Voronoi diagrams. The method supports distinct site shapes (points, line-segments, curved-arc segments, polygons, spheres, lines, polyhedra, etc.), different distance functions (Euclidean distance, convex distance functions, etc.) and is restricted to diagrams with connected Voronoi regions.
The presented approach constructs a tree (a quadtree in 2D/an octree in 3D) which encodes in its nodes and in a compact way all the information required for generating an explicit representation of the boundaries of the Voronoi diagram approximation. Then, by using this hierarchical data structure a reconstruction strategy creates the diagram approximation. We also present the algorithms required for dynamically maintaining under the insertion or deletion of sites the Voronoi diagram approximation. The main features of our approach are its generality, efficiency, robustness and easy implementation.
The presented approach constructs a tree (a quadtree in 2D/an octree in 3D) which encodes in its nodes and in a compact way all the information required for generating an explicit representation of the boundaries of the Voronoi diagram approximation. Then, by using this hierarchical data structure a reconstruction strategy creates the diagram approximation. We also present the algorithms required for dynamically maintaining under the insertion or deletion of sites the Voronoi diagram approximation. The main features of our approach are its generality, efficiency, robustness and easy implementation.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
Keywords:
computational geometry; computer graphics; generalized Voronoi diagram; approximation; dynamic maintenance; graphical examples; numerical examples; Euclidean distance; convex distance functions; algorithmsReferences:
| [1] | DOI: 10.1080/13658810110038942 · doi:10.1080/13658810110038942 |
| [2] | DOI: 10.1145/116873.116880 · doi:10.1145/116873.116880 |
| [3] | DOI: 10.1016/B978-044482537-7/50006-1 · doi:10.1016/B978-044482537-7/50006-1 |
| [4] | Behnke, S. Local Multiresolution path planning. Proceedings of 7th RoboCup International Symposium, |
| [5] | de Berg M., Computational Geometry: Algorithms and applications (1997) |
| [6] | Boada I., Eurographics 2002 Short Presentation pp 349– (2002) |
| [7] | Boada, I., Coll, N. and Sellarès, J. A. 2003.Dynamically Maintaining a Hierarchical Planar Voronoi Diagram Approximation, 836–846. Springer-Verlag. ICCSA 2003, Lecture Notes on Computer Science 2669 · Zbl 1327.65035 |
| [8] | Boada, I., Coll, N., Madern, N. and Sellarès, J. A. Approximations of 3D Generalized Voronoi Diagrams. Proceedings of 21th European Workshop on Computational Geometry, pp.163–166. · Zbl 1102.68671 |
| [9] | Chiang Y. J., Proceedings of IEEE, Special Issue on Computational Geometry 80 pp 362– (1992) |
| [10] | DOI: 10.1006/gmip.1997.0444 · doi:10.1006/gmip.1997.0444 |
| [11] | DOI: 10.1109/38.365006 · doi:10.1109/38.365006 |
| [12] | Coll, N., Hurtado, F. and Sellarès, J. A. Approximating planar subdivisions and generalized Voronoi diagrams from random sections. Proceedings of 19th European Workshop on Computational Geometry, pp.27–30. |
| [13] | Coll N., Universitat Politècnica de Catalunya (2004) |
| [14] | DOI: 10.1007/BF01553877 · Zbl 0664.68023 · doi:10.1007/BF01553877 |
| [15] | DOI: 10.1016/S0010-4485(98)00065-7 · Zbl 1034.68558 · doi:10.1016/S0010-4485(98)00065-7 |
| [16] | DOI: 10.1016/S0925-7721(01)00056-6 · Zbl 0997.68148 · doi:10.1016/S0925-7721(01)00056-6 |
| [17] | DOI: 10.1016/0167-8396(94)90029-9 · Zbl 0796.65013 · doi:10.1016/0167-8396(94)90029-9 |
| [18] | DOI: 10.1142/S0218195998000291 · Zbl 1026.65010 · doi:10.1142/S0218195998000291 |
| [19] | DOI: 10.1016/0146-664X(79)90079-0 · doi:10.1016/0146-664X(79)90079-0 |
| [20] | Hoff, K., Culver, T., Keyser, J., Lin, M. and Manocha, D. Proceedings of SIGGRAPH’99. Fast computation of generalized Voronoi diagrams using graphics hardware, pp.277–286. ACM Press. |
| [21] | DOI: 10.1109/JRA.1986.1087051 · doi:10.1109/JRA.1986.1087051 |
| [22] | DOI: 10.1109/38.156016 · doi:10.1109/38.156016 |
| [23] | Lorensen, W. and Cline, H. E. International Conference on Computer Graphics and Interactive Techniques. Marching cubes: a high resolution 3D surface construction algorithm, pp.163–169. ACM Press. |
| [24] | Okabe A., Spatial Tessellations: Concepts and Application of Voronoi Diagrams (2000) · Zbl 0946.68144 · doi:10.1002/9780470317013 |
| [25] | DOI: 10.1016/S0010-4485(02)00085-4 · doi:10.1016/S0010-4485(02)00085-4 |
| [26] | Ramamurthy R., Voronoi diagrams and medial axes of planar domains with curved boundaries (1998) |
| [27] | Samet H., Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS (1993) |
| [28] | Santaló L. A., Integral Geometry and Geometric Probability (1976) · Zbl 0342.53049 |
| [29] | Teichmann M., Polygonal approximation of Voronoi diagrams of a set of triangles in three dimensions (1997) |
| [30] | DOI: 10.1142/S0218195998000114 · Zbl 1035.68542 · doi:10.1142/S0218195998000114 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
