A ce i ied con lic loca o o he inc emen al main enance o he
Delaunay g aph o semi-algeb aic se s
F an¸cois An on,
Depa men o Compu e Science, Uni e si y o B i ish Columbia,
201-2366 Main Mall, Vancou e , B.C., Canada, V6T 1Z4
Abs ac
Mos o he cu es and su aces encoun e ed in geome ic modelling a e de ined as he se o solu ions o a sys em
o algeb aic equa ions o inequali ies (semi-algeb aic se s). The Vo onoi diag am o a se o si es is a decomposi ion
o he space in o p oximal egions (one o each si e). Vo onoi diag ams ha e been used o answe p oximi y
que ies. The dual g aph o he Vo onoi diag am is called he Delaunay g aph. Only app oxima ions by conics can
gua an ee a p ope con inui y o he i s o de de i a i e a con ac poin s, which is necessa y o gua an eeing he
exac ness o he Delaunay g aph. The cen al idea o his pape is ha a (one ime) symbolic p ep ocessing may
accele a e he ce i ied nume ical e alua ion o he Delaunay g aph con lic loca o . The symbolic p ep ocessing
is he compu a ion o he implici equa ion o he gene alised o se o conics. The ce i ied compu a ion o he
Delaunay g aph con lic loca o elies on heo ems on he uniqueness o a oo in gi en in e als (Kan o o ich,
Moo e-K awczyk). Fo conics, he compu a ions ge much as e by conside ing only he implici equa ions o he
gene alised o se s.
Key wo ds: Delaunay g aph, semi-algeb aic se s, conics, con lic loca o
1. In oduc ion
Mos o he cu es and su aces encoun e ed in
geome ic modelling a e de ined as he se o com-
mon ze oes o a se o polynomials (algeb aic a i-
e ies) o subse s o algeb aic a ie ies de ined by
one o mo e algeb aic inequali ies (semi-algeb aic
se s). Many p oblems om di e en ields in ol e
p oximi y que ies like inding he nea es neigh-
bou , inding all he neighbou s, o quan i ying
he neighbou liness o wo objec s. The e ac ion
planning [´
OY85] p oblem ( ha add esses he op-
imal ajec o y o a obo a ound obs acles) in
obo ics and spa ial analysis and in luence zones
in Geog aphic In o ma ion Sys ems [VC90] a e
s ongly linked o ques ions o p oximi y among
eal-wo ld objec s in eal-wo ld en i onmen s.
The Vo onoi diag am [Vo 08] (see Fig. 1) o a se
o si es is a decomposi ion o he space in o p ox-
Email add ess: an [email protected] echnique.
(F anc¸ois An on).
imal egions (one o each si e). The p oximal e-
gion (o Vo onoi zone) o a si e is he locus o poin s
close o ha si e han o any o he one. Vo onoi
diag ams allow one o answe p oximi y que ies a -
e a que y poin has been loca ed in he Vo onoi
zone i belongs o. The Vo onoi diag am de ines a
neighbou hood ela ionship among si es: wo si es
a e neighbou s i , and only i , hei Vo onoi egions
a e adjacen . The g aph o his neighbou hood e-
la ionship is called he Delaunay g aph. The De-
launay g aph o si es in he plane sa is ies he ol-
lowing emp y ci cle c i e ion (see Fig. 2): no si e in-
e sec s he in e io o he ci cles ouching ( angen
o wi hou in e sec ing he in e io o ) he si es
ha a e he e ices o any iangle o he Delau-
nay g aph (see Fig. 3). The e ha e been a emp s
[OBS92] o compu e Vo onoi diag ams o cu es
by app oxima ing cu es by line segmen s o ci cu-
la a cs, bu he exac ness o he Delaunay g aph
is no gua an eed [RF99a]. Indeed, he Vo onoi di-
ag am is e y sensi i e o he o de o con inui y
a con ac poin s (see [RF99a]). Only app oxima-
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
Fig. 1. The Vo onoi diag am (ligh ) o a ci cle, an ellipse
and a hype bola (da k)
Fig. 2. The 3 emp y ci cles o he si es o Fig. 1
HYPERBOLA
CIRCLE
ELLIPSE
Fig. 3. The Delaunay g aph o he si es o Fig. 1
ions by conics can gua an ee a p ope con inui y
o he i s o de de i a i e a con ac poin s, which
is necessa y o gua an eeing he exac ness o he
Delaunay g aph [RF99a]. O he app oxima ion al-
go i hms ha e used a New on-Raphson scheme o
compu e and classi y Vo onoi e ices o cu es
wi h a a ional pa ame e isa ion [RF99a,RF99b].
These do no di ec ly add ess he exac ness o he
Delaunay g aph.
2. P elimina ies
We will ecall now he o mal de ini ions o he
Vo onoi diag am and o he Delaunay g aph. Fo
his pu pose, we need o ecall some basic de ini-
ions.
De ini ion 1 (Me ic) Le Mbe an a bi a y se .
A me ic on Mis a mapping d:M×M→R+
such ha o any elemen s a,b, and co M, he
ollowing condi ions a e ul illed: d(a, b) = 0 ⇔
a=b,d(a, b) = d(b, a), and d(a, c)≤d(a, b) +
d(b, c).(M, d)is hen called a me ic space, and
d(a, b)is he dis ance be ween aand b.
Le M=RN, and δdeno e he Euclidean dis-
ance be ween poin s. Le S={s1, ..., sm}⊂
M, m ≥2 be a se o mdi e en subse s o M,
which we call si es. The dis ance be ween a poin
xand a si e si⊂Mis de ined as d(x, si) =
in y∈si{δ(x, y)}.
De ini ion 2 (In luence zone) Fo si, sj∈S, si(=
sj, he in luence zone D(si, sj)o siwi h espec
o sjis: D(si, sj) = {x∈M|d(x, si)< d (x, sj)}.
De ini ion 3 (Vo onoi egion) The Vo onoi e-
gion V(si,S)o si∈Swi h espec o he se Sis:
V(si,S) = !sj∈S,sj"=siD(si, sj).
De ini ion 4 (Vo onoi diag am) The Vo onoi di-
ag am o Sis he union V(S) = "si∈S∂V(si,S)
o all egion bounda ies.
De ini ion 5 (Delaunay g aph) The Delaunay
g aph DG (S)o Sis he dual g aph o V(S)
de ined as ollows:
– he se o e ices o DG (S)is S,
– o each N−1−dimensional ace o V(S) ha
belongs o he common bounda y o V(si,S)and
o V(sj,S)wi h si, sj∈Sand si(=sj, he e is
an edge o DG (S)be ween siand sjand ecip-
ocally, and
– o each e ex o V(S) ha belongs o he com-
mon bounda y o V(si1,S),. . . ,V #siN+2 ,S$,
wi h ∀k∈{1, ..., N + 2}, sik∈Sall dis inc ,
he e exis s a comple e g aph KN+2 be ween he
sik, k ∈{1, ..., N + 2}, and ecip ocally. (see
example on Fig. 3).
Le us in oduce he gene alised o se and he
gene alised Vo onoi e ex. We place ou sel es in
he a ine space K2whe e K=C o he sake o
in oducing hose no ions in an easie way. While
he R−gene alised o se o νis he locus o he
cen es o ci cles o adius R ha a e angen o ν,
he ue R−o se o νis he locus o he cen es o
ci cles o adius R ha a e angen o νand do no
con ain any poin o νin i s in e io (see Fig. 4).
De ini ion 6 (gene alised Vo onoi e ex) A gen-
e alised Vo onoi e ex o h ee semi-algeb aic se s
S1,S2, and S3is a poin o in e sec ion o he
R−gene alised o se s o S1,S2, and S3(see Exam-
Ma ch 25-26, 2004 Se ille (Spain)
Fig. 4. The s ophoid and i s ue (le ) and gene alised
( igh ) o se s
Fig. 5. A gene alised Vo onoi e ex (do ) o h ee conics
( hick lines)
ple on Fig. 5).
3. The Delaunay g aph con lic loca o o
semi-algeb aic se s
Le X1, ..., XN+2, be semi-algeb aic se s
[BR90,BCR98]. A semi-algeb aic se Xiis de-
ined as: !si
j=1 " i,j
k=1 #x∈RN| i,j,k ⋆i,j,k 0$, whe e
i,j,k is a polynomial wi h eal coe icien s in he
a iables xi1, ..., xiNand ⋆i,j,k is ei he <o =,
o i= 1,2,3,4, j= 1, ..., siand k= 1, ..., i,j.
The Delaunay g aph con lic loca o de e mines
which ones o he maximal dimensional ace s o
he Delaunay g aph o N+ 1 semi-algeb aic se s
X1, ..., XN+1 would be changed by he addi ion o
he semi-algeb aic se XN+2.
Le us assume wi hou loose o gene ali y ha
each " i,j
k=1 #x∈RN| i,j,k ⋆i,j,k 0$ o each Xiis
de ined by a leas one non- i ial algeb aic equa-
ion (i.e. di e en om he ze o polynomial). I
ou s a ing assump ion is no alid in he case we
ea , we can make i alid by adding he equa-
ions co esponding o i,j,k = 0 o each (i, j, k)
such ha jis he index o a componen ha is no
de ined as in he assump ion and iis he index o
he semi-algeb aic se o which he componen be-
longs. Le us deno e Vias he in e sec ion o all he
V( i,j,k) such ha ⋆i,j,k is = o each i= 1,2,3,4.
Le Nibe he no mal space o Via he poin xi=
(xi1, ..., xiN). Each i,j,k de ining Viinduces N−1
polynomials ni,j,k,l wi h l= 1, ..., N −1 ha a e
he equa ions de ining he no mal o V( i,j,k) a
xi. A poin q= (y1, ..., yN) belongs o Nii i s co-
o dina es sa is y all he equa ions o he no mal
spaces o V( i,j,k) a xisuch ha ⋆i,j,k is =.
Fo a gi en q= (y1, ..., yN), le Mibe he he
se o poin s mi= (zi1, ..., ziN)∈Xisuch ha q
belongs o he no mal space o Via he poin mi.
In he gene al case, each se Miis a ini e se o
poin s. Howe e , i Vicon ains a po ion o hype -
sphe e P HS (q, ρ) cen e ed on q, hen Micon ains
ha po ion o hype sphe e. To ge in all cases a
ini e se o poin s mio Vi, we use Si=Miwhen
Miis ini e, and Si"P HS (q, ρ) = {wi} o an
a bi a y poin wio P HS (q, ρ) when Vicon ains
a po ion o hype sphe e P HS (q, ρ) cen e ed on q.
We a e now able o w i e he sys em o alge-
b aic equa ions and inequali ies ha de ine he
ou come o he Delaunay g aph con lic loca o .
Le us conside he map π:K3N→KNde ined
by π(xi, q, mi) = q.
The poin qis a he dis ance om he poin
xii , and only i , he dis ance be ween qand xiis
. This is exp essed algeb aically by he equa ion
di(q, xi) = (y1−xi1)2+...+(yN−xiN)2− 2= 0.
The gene alised -o se Oi o Xiis he image
by πo he poin s o K3Nde ined by he ollowing
sys em o equa ions and inequali ies:



























∃j∈[1, si],∀k∈[1, i,j],





















i,j,k (xi)⋆i,j,k 0
i ⋆i,j,k is “ = ”,









di(xi, q) = 0
∀l= 1, .., N −1, ni,j,k,l (xi, q) = 0
xi1(xi)&= 0 o . . . o xiN(xi)&= 0
The ue -o se o Xiis ob ained as he di e -
ence o he gene alised -o se Oi o Xiand he
union o each one o he images by πo he semi-
algeb aic se s de ined by he ollowing sys em o
equa ions and inequali ies o each poin mio Si:



























∃j∈[1, si],∀k∈[1, i,j],





















i,j,k (mi)⋆i,j,k 0
i ⋆i,j,k is “ = ”,









(mi) = 0
∀l= 1, .., N −1, ni,j,k,l (mi, q) = 0
d(mi, q)<0
I is ob ious ha a ue Vo onoi e ex o
20 h Eu opean Wo kshop on Compu a ional Geome y
Running ime abo e sys ems gene alised o se s
Gene al Sol e 6 min 38 s 12 min 37 s
G adien Sol e 2 h 56 min 10 s 2 min 26 s
Hessian Sol e 20 h 17 min 42 s 3 min 42 s
Table 1
Some unning ime esul s o ellipses
X1, ..., XN+1 is a poin o in e sec ion o he ue
−o se s o X1, ..., XN+1 espec i ely. A ue
Vo onoi e ex o X1, ..., XN+1 is a he dis ance
R om XN+2, o al e na i ely, a ue Vo onoi e -
ex o X1, ..., XN+1 belongs o he ue R−o se
o XN+2. Conside he N+ 2−dimensional poin s
whose i s Ncoo dina es a e he coo dina es o
a ue Vo onoi e ex o X1, ..., XN+1, and he e-
maining wo a e he dis ances be ween ha ue
Vo onoi e ex and X1, ..., XN+1, and Rbe ween
ha ue Vo onoi e ex and XN+2. The Delau-
nay g aph con lic loca o should epo all he
ue Vo onoi e ices such as he co esponding
N+ 2−dimensional poin s sa is y R− < 0.
We ha e e alua ed he Delaunay g aph con lic
loca o wi hou sol ing any in e media y sys em
by using an in e al analysis based lib a y (ALIAS
[Me 00]) o sol ing ze o-dimensional sys ems o
equa ions and inequali ies. The ce i ied compu a-
ion o he Delaunay g aph con lic loca o elies
on heo ems on he uniqueness o a oo in gi en in-
e als (Kan o o ich and Moo e-K awczyk). This
compu a ion uses a bisec ion p ocess on one o
all he a iables using ei he only he equa ions o
he sys em, o using he Jacobian o he sys em
(Moo e-K awczyk es o inding “exac ly” he so-
lu ions), o using he Jacobian and he Hessian o
he sys em (wi h Kan o o ich, Moo e-K awczyk
es s). We i s used ALIAS on he abo e sys em
o algeb aic equa ions and inequali ies ha spec-
i y he Delaunay g aph con lic loca o o semi-
algeb aic se s. Then o conics, we used ALIAS on
he sys em simpli ied by eplacing he equa ions i,
niand dio he conics, no mals and dis ances be-
ween he poin s on he conics and he ue Vo onoi
e ex by he implici equa ions o he gene alised
o se s o he conics (see [An 04]). This induces
much as e compu a ions (see Table 1).
4. Conclusions
We ha e p esen ed wha we belie e is he i s
ce i ied con lic loca o o he inc emen al main-
enance o he Delaunay g aph o semi-algeb aic
se s. Fu he esea ch will y o imp o e he un-
ning ime o he compu a ions.
Re e ences
[An 04] F an¸cois An on. Vo onoi diag ams o semi-
algeb aic se s. PhD hesis, Uni e si y o B i ish
Columbia, Janua y 2004.
[BCR98] Jacek Bochnak, Michel Cos e, and Ma ie-
F an¸coise Roy. Real algeb aic geome y. Sp inge -
Ve lag, Be lin, 1998. T ansla ed om he 1987
F ench o iginal, Re ised by he au ho s.
[BR90] Ricca do Benede i and Jean-Jacques Risle . Real
algeb aic and semi-algeb aic se s. He mann,
Pa is, 1990.
[Me 00] Jean-Pie e Me le . Alias: an in e al analysis
based lib a y o sol ing and analyzing sys em o
equa ions. In SEA, Toulouse, F ance, 14–16 June
2000.
[OBS92] A suyuki Okabe, Ba y Boo s, and K¯okichi
Sugiha a. Spa ial essella ions: concep s and
applica ions o Vo ono¨ı diag ams. John Wiley &
Sons L d., Chiches e , 1992. Wi h a o ewo d by
D. G. Kendall.
[´
OY85] Colm ´
O’D´unlaing and Chee-K. Yap. A
“ e ac ion” me hod o planning he mo ion o
a disc. J. Algo i hms, 6(1):104–111, 1985.
[RF99a] Rajesh Ramamu hy and Rida T. Fa ouki.
Vo onoi diag am and medial axis algo i hm
o plana domains wi h cu ed bounda ies.
I. Theo e ical ounda ions. J. Compu . Appl.
Ma h., 102(1):119–141, 1999. Special issue:
compu a ional me hods in compu e g aphics.
[RF99b] Rajesh Ramamu hy and Rida T. Fa ouki.
Vo onoi diag am and medial axis algo i hm
o plana domains wi h cu ed bounda ies. II.
De ailed algo i hm desc ip ion. J. Compu . Appl.
Ma h., 102(2):253–277, 1999.
[VC90] Ch is ine Voi on-Canicio. Analyse spa iale
e analyse d’images pa la mo phologie
ma h´ema ique. RECLUS, 1990.
[Vo 08] Geo gi¨ı Feodose ich Vo ono¨ı. Nou elles
applica ions des pa am`e es con inus `a la h´eo ie
des o mes quad a iques. deuxi`eme m´emoi e.
eche ches su les pa all´elo`ed es p imi i s.
p emi`e e pa ie. pa i ion uni o me de l’espace
analy ique `a ndimensions `a l’aide des ansla ions
d’un mˆeme poly`ed e con exe. Jou nal ¨u die
eine und angewand e Ma hema ik, 134:198–287,
1908.