The predicates of the Apollonius diagram: Algorithmic analysis and implementation

被引:29
作者
Emiris, IZ [1 ]
Karavelas, MI
机构
[1] Univ Athens, Dept Informat & Telecommun, Athens 15784, Greece
[2] Univ Notre Dame, Dept Comp Sci & Engn, Notre Dame, IN 46556 USA
来源
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2006年 / 33卷 / 1-2期
关键词
computational geometry; algebraic computing; Apollonius diagram; geometric predicates; Sturm sequence; resultant;
D O I
10.1016/j.comgeo.2004.02.006
中图分类号
O29 [应用数学];
学科分类号
070104 [应用数学];
摘要
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 ail exact and efficient implementation of the algorithm, that handles all special cases. Among our tools we distinguish ail 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 oil 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. (c) 2005 Elsevier- B.V. All rights reserved.
引用
收藏
页码:18 / 57
页数:40
相关论文
共 35 条
[1]
ANGELIER P, 2002, THESIS U PARIS 7
[2]
[Anonymous], 1960, COMPLEX VARIABLES AP
[3]
[Anonymous], THESIS STANFORD U
[4]
ANTON F, 2002, P 18 EUR WORKSH COMP
[5]
POWER DIAGRAMS - PROPERTIES, ALGORITHMS AND APPLICATIONS [J].
AURENHAMMER, F .
SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :78-96
[6]
Berberich E, 2002, LECT NOTES COMPUT SC, V2461, P174
[7]
Boissonnat JD, 2003, SIAM PROC S, P305
[8]
Buchberger B., 1982, COMPUTING SUPPLEMENT, V4
[9]
DELAGE C, 2003, THESIS INRIA SOPHIA
[10]
DELAGE C, 2003, ECGTR241208701 INRIA