Sibson’s o mula o highe o de Vo onoi diag ams
Me cè Cla e ol1, And ea de las He as-Pa illa1, Clemens Hueme 1,
and Dolo es La a2
1 Uni e si a Poli ècnica de Ca alunya
[email p o ec ed], [email p o ec ed], [email p o ec ed]
2 Cen o de In es igación y de Es udios A anzados
[email p o ec ed]
Abs ac
Le
S
be a se o
n
poin s in gene al posi ion in
Rd
. The o de -
k
Vo onoi diag am o
S
,
Vk
(
S
), is a
subdi ision o
Rd
in o cells whose poin s ha e he same
k
nea es poin s o
S
. Sibson, in his seminal
pape om 1980 (A ec o iden i y o he Di ichle essella ion), gi es a o mula o exp ess a poin
Q
o
S
as a con ex combina ion o o he poin s o
S
by using a ios o olumes o he in e sec ion o
cells o
V2
(
S
)and he cell o
Q
in
V1
(
S
). The na u al neighbou in e pola ion me hod is based on
Sibson’s o mula. We gene alize his esul o exp ess
Q
as a con ex combina ion o o he poin s o
S
by using a ios o olumes om Vo onoi diag ams o any gi en o de .
1 In oduc ion
Le
S
be a se o
n
poin s in gene al posi ion in
Rd
, meaning no
m
o hem lie in a (
m−
2)-
dimensional la o
m
= 2
,
3
, ..., d
+ 1 and no
d
+ 2 o hem lie in he same
d
-sphe e, and le
k
be a na u al numbe wi h 1
≤k≤n−
1. Le
σd
deno e he Lebesgue measu e on
Rd
, o
simpli y we jus w i e σ.
The o de -
k
Vo onoi diag am o
S
,
Vk
(
S
), is a subdi ision o
Rd
in o cells such ha poin s
in he same cell ha e he same
k
nea es poin s o
S
. Thus, each cell
(
Pk
)o
Vk
(
S
)is de ined
by a subse
Pk
o
S
o
k
elemen s, whe e each poin o
(
Pk
)has
Pk
as i s
k
closes poin s
om
S
. Simila ly, he o de ed Vo onoi diag am o o de
k
o
S
,
OVk
(
S
), can be de ined as a
subdi ision o
Rd
in o cells such ha poin s in he same cell ha e he same o de ed
k
nea es
poin s o
S
. Thus, each cell
(
⟨Pk⟩
)o
OVk
(
S
)is de ined by an o de ed subse
⟨Pk⟩
o size
k
o
S
, whe e he poin s a e a anged in o de o p oximi y s a ing om he closes o he
a hes . No e ha , by de ini ion, he union o all he cells o
OVk
(
S
)co esponding o he
di e en pe mu a ions o a ixed subse o leng h
k
o
S
is he cell,
(
Pk
), associa ed o such
subse in he (o dina y) o de -kVo onoi diag am, Vk(S). See Figu e 1.
Fo he o de -
k
Vo onoi diag am o
S
, he egion
Rk
(
ℓ
)o
Qℓ∈S
is de ined as he se
o cells o
Vk
(
S
) ha ha e he poin
Qℓ
as one o hei
k
nea es neighbou s. See Figu e 2.
Fo
OVk
(
S
)we can de ine hese egions in he same way. These egions a e no necessa ily
con ex bu s a -shaped, see [
2
,
4
,
10
,
16
], and i is known ha
R1
(
ℓ
)is con ained in he
ke nel o
Rk
(
ℓ
); see [
3
]. Also, hese egions a e ela ed o B illouin zones. Fo a gi en
k
, he
egion
Rk
(
ℓ
)
Rk−1
(
ℓ
)is known as a B illouin zone o
Qℓ
. B illouin zones ha e been s udied
mainly o la ices bu also o a bi a y disc e e se s, see e.g. [6, 17].
Local coo dina es based on Vo onoi diag ams we e in oduced by Sibson [
13
]. He s a es
ha , gi en a se
S
o
n
poin s o
Rd
in gene al posi ion, a poin
Qℓ∈S
can be exp essed as
a con ex combina ion o i s nea es poin s o
S
. This is desc ibed nex . Cells o
V2
(
S
) ha
in e sec
(
{Qℓ}
)in
V1
(
S
)a e o he o m
(
{Qℓ, Qj}
), i.e., cells de ined by
Qℓ
and ano he
poin
Qj
, ha we call i s na u al neighbou . These in e sec ions gi e a ios o olumes
which a e he coe icien s mul iplying he co esponding na u al neighbou s in he con ex
40 h Eu opean Wo kshop on Compu a ional Geome y, Ioannina, G eece, Ma ch 13–15, 2024.
This is an ex ended abs ac o a p esen a ion gi en a Eu oCG’24. I has been made public o he bene i o he
communi y and should be conside ed a p ep in a he han a o mally e iewed pape . Thus, his wo k is expec ed
o appea e en ually in mo e inal o m a a con e ence wi h o mal p oceedings and/o in a jou nal.
21:2 Sibson’s o mula o highe o de Vo onoi diag ams
15
12
13
31
34
43
41
14
51
25
52
21
45
54
23
32
Q3
Q4
Q5
Q1
Q2
135
153
134
314
341
431
132
123
125
152
215
213
312
251
521
512
514
154
541
451
415
145
143
413
231
321
513
Q3
Q4
Q5
Q1
Q2
Figu e 1 Fo a se
S
=
{Q1,··· , Q5}
o i e poin s in
R2
. Each cell o
OVk
(
S
)is labeled by he
indices o i s
k
nea es poin s o
S
.
V1
(
S
)is shown in black,
V2
(
S
)in g een, and
V3
(
S
)in o ange
colou . Le : The cells o
OV2
(
S
)wi h he same nea es neighbou
Qi
om
S
o m he cell
(
{Qi}
)
in
V1
(
S
). The cells o
OV2
(
S
)wi h he same subse
P2
o wo poin s o
S
(in any o de ) o m he
cell (P2)o V2(S). Righ : OV3(S)is shown oge he wi h V1(S),V2(S), and V3(S).
Q2
Q3
Q4
Q5
Q6
Q8
Q9
Q0
V2(S)
Q7
Q1
V1(S)
R1(1)
R2(1)
Figu e 2
R1
(1) is he cell
(
{Q1}
)in
V1
(
S
).
R2
(1) is he union o cells o
V2
(
S
) ha ha e
Q1
as
one o i s wo nea es neighbou s. R1(1) ⊂R2(1).
combina ion ha exp esses
Qℓ
. Volumes
σ
(
(
{Qℓ, Qj}
)
∩
(
{Qℓ}
)) a e equal o he olumes
gi en by he in e sec ion o he cells o V1(S {Qℓ})and (Qℓ)in V1(S), see Figu e 3.
M. Cla e ol, A. de las He as-Pa illa, C. Hueme and D. La a 21:3
▶Theo em 1.1. (Local coo dina es p ope y [13]). Fo a bounded cell ({Qℓ})o V1(S),
Qℓ=X
j=ℓ
σ( ({Qℓ, Qj})∩ ({Qℓ}))
σ( ({Qℓ})) Qj(1)
Sibson’s o mula has been used o de ine he na u al neighbou in e pola ion me hod [
14
].
Gi en a se o poin s and a unc ion, his in e pola ion me hod p o ides a smoo h app oxima-
ion o new poin s o he unc ion. Sibson’s algo i hm uses he closes subse o he inpu se
S {Qℓ}
o in e pola e a que y poin ,
Qℓ
, and applies weigh s based on he a ios o olumes
p o ided by Theo em 1.1. Local coo dina es and he na u al neighbou in e pola ion me hod
ha e been s udied e.g. in [
5
,
11
,
15
], and hey ha e many applica ions such as econs uc ion
o a su ace om uns uc u ed da a o in e pola ion o ain all da a, see [9, 15].
Q3
Q2
Q`
Q1
Q6
Q5
Q4
Figu e 3 In
R2
. Le : The ini ial Vo onoi diag am
V1
(
S {Qℓ}
)wi hou que y poin
Qℓ
. Righ :
Colo ed a eas gi en by he in e sec ions o
(
{Qℓ}
)and he cells o
V1
(
S {Qℓ}
), a e he same as
he ones gi en by he in e sec ions o he cells o V2(S)(shown in dashed) wi h he cell ({Qℓ}).
Au enhamme ga e a gene aliza ion o Sibson’s esul o Vo onoi diag ams o highe o de ,
and mo e gene ally o powe diag ams, see [
1
]. Au enhamme ’s o mula allows o w i e a
poin
Qℓ
o
S
as a linea combina ion o o he poin s o
S
. We s a e his in Theo em 2.1
and Co olla y 2.2 below. The o mula in Theo em 2.1 is de ined in e ms o
OVk+1
(
S
). I is
es a ed in Co olla y 2.2 in e ms o in e sec ions o cells o
Vk−1
(
S
)and
Vk+1
(
S
)wi h a cell
o Vk(S). This o mula wo ks o a bounded cell o Vk(S).
Ou main con ibu ion is ano he gene aliza ion o Sibson’s esul , s a ed in Theo em 2.3.
In his heo em, we exp ess a poin
Qℓ∈S
as a con ex combina ion o i s neighbou s o
S
using a ios o olumes in he egion
Rk
(
ℓ
). Simila o Sibson’s o mula ha equi ed he
cell o he poin
Qℓ
o be bounded, ou o mula equi es i s egion
Rk
(
ℓ
) o be bounded. Fo
he case k= 1, Theo em 2.3 coincides wi h Theo em 1.1.
This pape is o ganized as ollows. Sec ion 2 de ails he gene aliza ion o Sibson’s o mula.
In Sec ion 3 we gi e a geome ic in e p e a ion o he o mulas p esen ed in Sec ion 2 o
poin se s in he plane. Finally, Sec ion 4 is on how he gene aliza ion o Sibson’s o mula
could be used o in e pola ion. P oo s a e omi ed in his abs ac .
Eu oCG’24
21:4 Sibson’s o mula o highe o de Vo onoi diag ams
2 Coo dina es based on Vo onoi diag ams
In his sec ion we p esen a gene aliza ion o Sibson’s o mula ha exp esses a poin using
i s neighbou s o he Vo onoi diag am o any gi en o de . Fo his, we ecall esul s om
Au enhamme [1] in Theo em 2.1 and Co olla y 2.2, using a di e en no a ion.
Le
Fk+1
(
Pk
), o simpli y
F
(
Pk
), be he se o cells o
OVk+1
(
S
),1
≤k≤n−
2, whose
k
nea es neighbou s a e he poin s o
Pk⊂S
in any o de , and he (
k
+ 1)- h nea es
neighbou is ano he poin o
S
no in
Pk
. Le
i,j
deno e he union o cells o
OVk+1
(
S
)
whose k- h nea es neighbou is Qiand whose (k+ 1)- h nea es neighbou is Qj.
▶Theo em 2.1. ([1]) I all cells in F(Pk)a e bounded in OVk+1(S), hen
X
j
i,j ∈F(Pk)
σ( i,j)Qi=X
i
i,j ∈F(Pk)
σ( i,j)Qj
Q1
Q6
Q3
Q4
5,1∪ 5,3
2,1∪ 2,3∪ 2,6
Q5
Q2
Q1
Q6
Q3
Q4
Q5
2,1∪ 5,1
2,3∪ 5,3
2,6
Q2
Figu e 4 Illus a ing Theo em 2.1 o
F
(
{Q2, Q5}
)in
OV3
(
S
), whe e
S
is a se o six poin s in
R2
. In his case he equa ion educes o
σ
(
5,1∪ 5,3
)
Q5
+
σ
(
2,1∪ 2,3∪ 2,6
)
Q2
=
σ
(
2,1∪ 5,1
)
Q1
+
σ( 2,3∪ 5,3)Q3+σ( 2,6)Q6. Le : cells g ouped acco ding o i s k-nea es neighbou . Righ : cells
g ouped acco ding o i s (k+ 1)-nea es neighbou .
No e ha , he subdi isions induced by
Vk−1
(
S
)a he in e io o
(
Pk
)co espond o
g ouping he cells o
F
(
Pk
)in
OVk+1
(
S
) ha ha e he same
k
-nea es neighbou . Also, he
subdi isions induced by
Vk+1
(
S
)a he in e io o
(
Pk
)co espond o g ouping he cells o
F(Pk)in OVk+1(S) ha ha e he same (k+ 1)-nea es neighbou . See Figu e 4.
By hese obse a ions, Theo em 2.1 can be s a ed as ollows.
▶Co olla y 2.2. ([1]) Le 2≤k≤n−2and le (Pk)be a bounded cell o Vk(S). Then,
X
(Pk−1)∈Vk−1(S)
Qi∈Pk Pk−1
σ( (Pk−1)∩ (Pk))Qi=X
(Pk+1)∈Vk+1(S)
Qj∈Pk+1 Pk
σ( (Pk+1)∩ (Pk))Qj
No e ha , by he ela ion be ween he Vo onoi diag ams and he o de ed Vo onoi diag ams,
Rk
(
ℓ
)is he se o cells o
OVk+1
(
S
) ha ha e
Qℓ
as one o hei
k
nea es neighbou s om
S
, i.e.,
Rk
(
ℓ
) =
∪Qℓ∈PkF
(
Pk
). Based on his obse a ion and Theo em 2.1 we can p o e he
ollowing esul .
▶Theo em 2.3. I Rk(ℓ)is a bounded egion, hen
Qℓ=X
i
i,j ∈Rk(ℓ)
σ( i,j)
σ(Rk(ℓ))Qj.
M. Cla e ol, A. de las He as-Pa illa, C. Hueme and D. La a 21:5
▶Co olla y 2.4. Le 1≤k≤n−2and le Rk(ℓ)be a bounded egion. Then,
Qℓ=X
(Pk)∈Rk(ℓ)X
(Pk+1)∈Vk+1(S)
Qj∈Pk+1 Pk
σ( (Pk+1)∩ (Pk))
σ(Rk(ℓ)) Qj
3 A geome ic in e p e a ion
In he ollowing we examine he gene aliza ion o Sibson’s heo em o highe o de Vo onoi
diag ams om Co olla y 2.2 in mo e de ail o cells
(
Pk
)o
Vk
(
S
), when
S
is a poin se in
R2
. Di ide bo h sides o he equa ion gi en in Co olla y 2.2 by
σ
(
(
Pk
)); hen, each side o
he equa ion desc ibes a poin H ha is a con ex combina ion o poin s om S. We ha e
H=X
(Pk−1)∈Vk−1(S)
Qi∈Pk Pk−1
σ( (Pk−1)∩ (Pk))
σ( (Pk)) Qi=X
(Pk+1)∈Vk+1(S)
Qj∈Pk+1 Pk
σ( (Pk+1)∩ (Pk))
σ( (Pk)) Qj(2)
Wha can we say abou his poin H?
Le
(
Pk
)be an
-gon. Then
S
con ains
poin s
Q1, . . . , Q
, such ha each edge o he
-gon lies on a pe pendicula bisec o be ween wo o hese
poin s, and each e ex,
Cijℓ
,
o
(
Pk
)is he cen e o a ci cle passing h ough h ee o hem,
Qi
,
Qj
, and
Qℓ
; see e.g. [
3
].
We deno e wi h ∆(
ABC
) he iangle wi h e ices
A
,
B
, and
C
, and wi h
□
(
ABCD
)
he quad ila e al wi h e ices A, B, C and D, in cyclic o de .
Le us conside he case when
(
Pk
)is a quad ila e al cell o
Vk
(
S
)wi h e ices
C123
,
C124, C134
, and
C234
, in cyclic o de along he bounda y o he quad ila e al cell
(
Pk
) =
□
(
C123C124C134C234
). One o he diagonals
C123C134
and
C124C234
is an edge o
Vk−1
(
S
)
and he o he one o
Vk+1
(
S
). Figu e 5 shows an example. We e e o [
3
,
7
] o a mo e
de ailed discussion on he s uc u e o cells o Vk(S). Co olla y 2.2 s a es in his case ha
H=Q1·σ(∆(C123C134C234))
σ(□(C123C124C134C234)) +Q3·σ(∆(C123C124C134))
σ(□(C123C124C134C234))
=Q2·σ(∆(C124C134C234))
σ(□(C123C124C134C234)) +Q4·σ(∆(C124C234C123))
σ(□(C123C124C134C234)) (3)
I ollows ha
H
is he in e sec ion poin o diagonals
Q1Q3
and
Q2Q4
o
□
(
Q1Q2Q3Q4
)
.
This implies ha gi en a quad ila e al cell
□
(
C123C124C134C234
)o
Vk
(
S
), he ou co e-
sponding poin s o
S
also o m a con ex quad ila e al,
□
(
Q1Q2Q3Q4
)
.
Mo eo e , we can
show ha a eas o iangles wi h e ices in
□
(
C123C124C134C234
)a e p opo ional o a eas
o iangles wi h e ices in □(Q1Q2Q3Q4), also see [8, 12].
Le us hen conside he case when
(
Pk
)is a cell o
Vk
(
S
)wi h mo e han ou sides.
Equa ion (2) gi es a poin
H
ha can be exp essed in wo ways as con ex combina ion o
poin s o
S
. Le us look a a pen agonal cell
(
Pk
) = (
C123C134C145C245C125
)o
Vk
(
S
);
See Figu e 6. Fo > 5 he si ua ion is simila . Co olla y 2.2 he e gi es
H=Q1·σ(□(C123C125C145C134))
σ( (C123C134C145C245C125)) +Q5·σ(∆(C125C245C145))
σ( (C123C134C145C245C125))
=Q2·σ(□(C245C125C123C234))
σ( (C123C134C145C245C125)) +Q4·σ(∆(C245C234C1345C145))
σ( (C123C134C145C245C125))
+Q3·σ(∆(C123C234C134))
σ( (C123C134C145C245C125))
Eu oCG’24

21:6 Sibson’s o mula o highe o de Vo onoi diag ams
Q1
Q3
Q2
Q4
b23
b12
b34
b14
H
C124
C123
C234
C134
Figu e 5 The quad ila e al cell
(
Pk
) =
□
(
C123C124C134C234
)o
Vk
(
S
)is ob ained by pe pen-
dicula bisec o cons uc ion om
{Q1, Q2, Q3, Q4} ⊂ S.
Poin
H
gi en by Equa ion (2) is he
in e sec ion poin o diagonals Q1Q3and Q2Q4.T iangles wi h same colo ha e p opo ional a ea.
We ge ha
H
lies on he segmen
Q1Q5
and inside he iangle ∆(
Q2Q3Q4
). Fu he -
mo e,
H
di ides he segmen
Q1Q5
in he same p opo ion as he edge
C125C145
di ides he
pen agon (
C123C134C145C245C125
)in o he he quad ila e al
□
(
C125C145C134C123
)and he
iangle ∆(
C125C145C245
). And
H
di ides iangle ∆(
Q1Q2Q3
)in he same p opo ion in o
iangles ∆(
Q3HQ4
),∆(
Q2HQ3
), and ∆(
Q2HQ4
)as
C234
di ides (
C123C134C145C245C125
)
in o □(C245C125C123C234),□(C245C234C134C145)and ∆(C134C234C123).
4 Towa ds highe o de na u al neighbou in e pola ion
Sibson’s heo em (Theo em 1.1) ga e ise o he na u al neighbou in e pola ion me hod.
Gi en a se o poin s
S
and known unc ion alues
G
(
Qj
) o
Qj∈S {Qℓ}
, he unc ion
alue
G
(
Qℓ
)o a poin
Qℓ
is in e pola ed by
G
(
Qℓ
) =
PjcjG
(
Qj
), whe e he sum is o e
he na u al neighbou s
Qj
o
Qℓ
in
V1
(
S
). The local coo dina es
cj
a e gi en by Theo em 1.1.
No e ha hey sa is y
Pjcj
= 1 and
cj≥
0 o all
j
. Then, Sibson’s na u al neighou
in e pola ion is gi en by
G(Qℓ) = X
j=ℓ
σ( ({Qℓ, Qj})∩ ({Qℓ}))
σ( ({Qℓ})) G(Qj).(4)
The gene aliza ion o Sibson’s o mula gi en in Theo em 2.3 sugges s o app oxima e he
unc ion alue
G
(
Qi
)by using he na u al neighbou s o highe o de Vo onoi diag ams. By
using he egion Rk(ℓ) o k > 1, we can es ima e he unc ion alue o a poin Qℓas
G(Qℓ) = X
i
i,j ∈Rk(ℓ)
σ( i,j)
σ(Rk(ℓ))G(Qj).(5)
No e ha R1(ℓ) = ({Qℓ})in V1(S), and o k= 1 Equa ions (4) and (5) coincide.
A be e es ima ion can be ob ained by using Theo em 2.3 in a combina ion o di e en
alues o k. We explo e his o he 1-dimensional case.
M. Cla e ol, A. de las He as-Pa illa, C. Hueme and D. La a 21:7
Q2
Q3
Q5
Q4
V1(S)
V2(S)
V3(S)
OV3(S)
F(P2)
P2={Q1,Q5}
Q1
C245
H
C234
Q1
C245
C125
C123
C134
C145
Q2
Q3
Q5
Q4
Figu e 6 (Le )
OV3
(
S
) o a se o i e poin s
S
=
{Q1, Q2, Q3, Q4, Q5}.
Fo
P2
=
{Q1, Q5}
, he
g ey egion
F
(
P2
)o
OV3
(
S
)is he pen agonal cell
(
P2
)o
V2
(
S
)
.
(
P2
)is di ided by an edge o
V1
(
S
)and is also di ided by h ee edges o
V3
(
S
). (Righ ) The poin
H
lies on he segmen
Q1Q5
and inside he iangle ∆(
Q2, Q3, Q4
). T iangle a eas o ∆(
Q2HQ3
)
,
∆(
Q3HQ4
)and ∆(
Q2HQ4
)
a e p opo ional o he a eas o he h ee colo ed egions inside
(
P2
), g een, yellow, and pink,
espec i ely. The leng hs o segmen s
HQ1
and
HQ5
a e p opo ional o he a eas
σ
(
(
P2
)
∩
(
{Q1}
))
and σ( (P2)∩ ({Q5})), espec i ely.
Theo em 2.3, espec i ely Co olla y 2.4, o dimension 1 educes o he ollowing s a emen .
▶P ope y 4.1. Le S={x0, x1,...x2ℓ}wi h x0< x1< . . . < x2ℓbe eal numbe s. Then,
xℓ=1
x2ℓ−x0 ℓ−1
X
i=0
xi(xℓ+1+i−xℓ+i)!+ 2ℓ
X
i=ℓ+1
xi(xi−ℓ−xi−ℓ−1)!!.(6)
▶
Rema k. P ope y 4.1 has ac ually a mo e gene al s a emen . The assump ion
x0< x1<
. . . < x2ℓis no needed.
We deno e poin s
Qi
o
S
as
xi
and hei unc ion alues
G
(
Qi
)as
yi
. When
k
= 1 we
ha e Sibson’s classical nea es neighbou in e pola ion, which o dimension
d
= 1 is piecewise
linea in e pola ion. Le
x0, x1, . . . , x5
be six poin s on he eal line in ha o de . And le
x2< x < x3
be a que y poin whose unc ion alue
G
(
x
)we wan o in e pola e. To a oid
degene a e cases whe e bisec o s be ween poin s coincide, we also assume ha all midpoin s
(
xi
+
xj
)
/
2wi h
xi, xj∈ {S∪{x}}
a e di e en . Sibson’s classical o mula, Equa ion (4),
uses he wo neighbou s x2and x3o x, and gi es he in e pola ion
G1(x) = 1
x3−x2
(y2(x3−x) + y3(x−x2)),(7)
i.e. poin (
x, G1
(
x
)) lies on he line segmen connec ing poin s (
x2, y2
)and (
x3, y3
)
.
This can
also be deduced om P ope y 4.1. Combining Equa ion (5) o
k
= 1 and
k
= 2, we ob ain
Eu oCG’24
21:8 Sibson’s o mula o highe o de Vo onoi diag ams
G2(x) = 1
x4−x1+x3−x2
(y1(x3−x) + y2(x4−x) + y3(x−x1) + y4(x−x2)).(8)
In he same way, combining Equa ion (5) o k= 1,k= 2, and k= 3, we ob ain
G3(x) = 1
x5−x0+x4−x1+x3−x2
(y0(x3−x) + y1(x4−x) + y2(x5−x)
+y3(x−x0) + y4(x−x1) + y5(x−x2)).(9)
Figu e 7 shows an example o he in e pola ion o mulas gi en in Equa ions (7), (8), and (9).
11 22 33 44 55 66 77 88
-2-2
-1-1
11
22
33
44
55
66
00
yy00
yy11
yy22
yy33
yy44
yy55
Figu e 7 The gene alized Sibson in e pola ion in
R1
. In g een: Sibson’s o iginal in e pola ion,
Equa ion (7), used only
R1
(
x
). The blue segmen shows he in e pola ion using
R1
(
x
)and
R2
(
x
),
gi en by Equa ion (8). Fou poin s a e used. The ed segmen shows he in e pola ion using
R1
(
x
)
,
R2(x),and R3(x), gi en by Equa ion (9). Six poin s a e used.
We conclude wi h some commen s on he p oposed in e pola ion o mulas. Fi s , hey
appea in a na u al way om he gene aliza ion o Sibson’s o mula. This al eady makes
i wo h o s udy such gene alized in e pola ion o mulas. In Equa ions (8) and (9), he
coe icien s
cj
in
Gi
(
x
) =
Pjcjyj
,
i
= 2
,
3, sa is y
Pjcj
= 1 and
cj≥
0 o e e y
cj.
We
also men ion ha i can no be gua an eed ha
Gi
(
x
)coincides wi h
Gi
(
x2
)o wi h
Gi
(
x3
),
when
x
coincides wi h one o he endpoin s o he in e al,
x2
o
x3
, espec i ely. Though,
we obse e ha in his case, he poin a hes away om
x
on one side, d ops om being
used in he in e pola ion o mula. This also holds o he classical case k= 1.
Finally, we expec ha he gene alized in e pola ion o mulas can ha e applica ions. Fo
ins ance, when he used alues o he in e pola ion a e ob ained by measu emen s and
measu emen inaccu acy can no be uled ou . Then eliabili y migh be imp o ed by using
nea es neighbou s om Vk(S)o by using Rk(x), ins ead o only V1(S).
Acknowledgemen s
This esea ch has been suppo ed by p ojec s 2021SGR00266 and PID2019-104129GB-I00/
MCIN/ AEI/ 10.13039/501100011033.
Re e ences
1
F anz Au enhamme . Linea combina ions om powe domains. Geome iae dedica a,
28(1):45–52, 1988.
M. Cla e ol, A. de las He as-Pa illa, C. Hueme and D. La a 21:9
2
F anz Au enhamme and O ied Schwa zkop . A simple on-line andomized inc emen al
algo i hm o compu ing highe o de o onoi diag ams. In P oceedings o he se en h
annual symposium on Compu a ional geome y, pages 142–151, 1991.
3
Me cè Cla e ol, And ea de las He as Pa illa, Clemens Hueme , and Alejand a Ma ínez-
Mo aian. The edge labeling o highe o de Vo onoi diag ams. 2021.
h ps://a xi .o g/
abs/2109.13002.
4
He be Edelsb unne and Mabel Iglesias-Ham. Mul iple co e s wi h balls i: Inclusion–
exclusion. Compu a ional Geome y, 68:119–133, 2018.
5
Ge ald Fa in. Su aces o e Di ichle essella ions. Compu e aided geome ic design,
7(1-4):281–292, 1990.
6
Ga e h A Jones. Geome ic and asymp o ic p ope ies o B illouin zones in la ices. Bulle in
o he London Ma hema ical Socie y, 16(3):241–263, 1984.
7
De -Tsai Lee. On k-nea es neighbo Vo onoi diag ams in he plane. IEEE T ansac ions on
Compu e s, C-31(6):478–487, 1982.
8
Ma ia Fla ia Mammana and Biagio Micale. Quad ila e als o iangle cen es. The Ma he-
ma ical Gaze e, 92:466–475, 2008.
9
A suyuki Okabe, Ba y Boo s, and Kokichi Sugiha a. Nea es neighbou hood ope a ions wi h
gene alized Vo onoi diag ams: a e iew. In e na ional Jou nal o Geog aphical In o ma ion
Sys ems, 8(1):43–71, 1994.
10
A suyuki Okabe, Ba y Boo s, Kokichi Sugiha a, and Sung Nok Chiu. Spa ial essella ions:
concep s and applica ions o Vo onoi diag ams. 2009.
11
B uce R. Pipe . P ope ies o local coo dina es based on Di ichle essella ions. In Geome ic
modelling, pages 227–239. Sp inge , 1993.
12
Olga Radko and Emmanuel Tsuke man. The pe pendicula bisec o cons uc ion, he
iso opic poin , and he Simson line o a quad ila e al. Fo um Geome ico um, 12:161–189,
2012.
13
Robin Sibson. A ec o iden i y o he Di ichle essella ion. In Ma hema ical P oceedings
o he Camb idge Philosophical Socie y, olume 87, pages 151–155. Camb idge Uni e si y
P ess, 1980.
14
Robin Sibson. A b ie desc ip ion o na u al neighbou in e pola ion. In e p e ing mul i-
a ia e da a, pages 21–36, 1981.
15
Kokichi Sugiha a. Su ace in e pola ion based on new local coo dina es. Compu e -Aided
Design, 31(1):51–58, 1999.
16
G Fejes Tó h. Mul iple packing and co e ing o he plane wi h ci cles. Ac a Ma h. Acad.
Sci. Hunga , 27(1-2):135–140, 1976.
17
JJP Vee man, Mau icio M Peixo o, And é C Rocha, and Sco Su he land. On B illouin
zones. Communica ions in Ma hema ical Physics, 212:725–744, 2000.
Eu oCG’24