Name
Abstract | ||
|---|---|---|
We study the predicates involved in an efficient dynamic algorithm for computing the Apollonius diagram in the plane, also known as the additively weighted Voronoi diagram. We present a complete algorithmic analysis of these predicates, some of which are reduced to simpler and more easily computed primitives. This gives rise to an exact and efficient implementation of the algorithm, that handles all special cases. Among our tools we distinguish an inversion transformation and an infinitesimal perturbation for handling degeneracies.The implementation of the predicates requires certain algebraic operations. In studying the latter, we aim at minimizing the algebraic degree of the predicates and the number of arithmetic operations; this twofold optimization corresponds to reducing bit complexity. The proposed algorithms are based on static Sturm sequences. Multivariate resultants provide a deeper understanding of the predicates and are compared against our methods. We expect that our algebraic techniques are sufficiently powerful and general to be applied to a number of analogous geometric problems on curved objects. Their efficiency, and that of the overall implementation, are illustrated by a series of numerical experiments. Our approach can be immediately extended to the incremental construction of abstract Voronoi diagrams for various classes of objects. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.comgeo.2004.02.006 | Comput. Geom. |
Keywords | DocType | Volume |
resultant 2000 msc: 68u05,computational geometry,algebraic technique,algorithmic analysis,resultant,geometric predicates,algebraic computing,overall implementation,proposed algorithm,additively weighted voronoi diagram,sturm sequence,efficient dynamic algorithm,algebraic degree,apollonius diagram,certain algebraic operation,efficient implementation,abstract voronoi diagram,68w30,voronoi diagram | Journal | 33 |
Issue | ISSN | Citations |
1-2 | Computational Geometry: Theory and Applications | 28 |
PageRank | References | Authors |
1.29 | 21 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ioannis Z. Emiris | 1 | 949 | 100.40 |
| Menelaos I. Karavelas | 2 | 229 | 18.99 |