Approximations of 2D and 3D generalized Voronoi diagrams
| Autor: | Narcis Madern, Imma Boada, J. Antoni Sellarès, Narcís Coll |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Mathematical diagram
Applied Mathematics Computer Science::Computational Geometry Lloyd's algorithm Topology Weighted Voronoi diagram Computer Science Applications Bowyer–Watson algorithm Combinatorics Fortune's algorithm Computational Theory and Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Power diagram Voronoi diagram Centroidal Voronoi tessellation ComputingMethodologies_COMPUTERGRAPHICS Mathematics |
| Zdroj: | International Journal of Computer Mathematics. 85:1003-1022 |
| ISSN: | 1029-0265 0020-7160 |
| DOI: | 10.1080/00207160701466362 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |