Sibson’s formula for higher order Voronoi diagrams

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