Dualitás az origón át nem haladó egyenesek és az origótól különbözõ pontok között:
e origót elkerülõ egyenes -> ax+by=1 ``tengelymetszetes egyenlet'' -> (a,b)/=(0,0) számpár.
P origótól különbözõ pont -> (a,b)/=(0,0) számpár.
Az (a,b)/=(0,0) számpár által jelölt pontot (a,b)-vel jelöljük. Az (a,b)/=(0,0) számpár által jelölt egyenest (a,b)^*-gal jelöljük.
Lemma: (i) (a,b) akkor és csak akkor illeszkedik (c,d)^*-re, ha ac+bd=1. (ii) (a,b) akkor és csak akkor esik (c,d)^* origót tartalmazó oldalára, ha ac+bd<1. (iii) (a,b) akkor és csak akkor esik (c,d)^* origót nem tartalmazó oldalára, ha ac+bd>1.
Lemma: (i) (a_1,b_1),(a_2,b_2),(a_3,b_3),... pontok akkor és csak akkor esnek egy origón át nem haladó egyenesre, ha (a_1,b_1)^*,(a_2,b_2)^*,(a_3,b_3)^*,... egyenesek egy origótól különbözõ ponton haladnak át. (ii) (a_1,b_1),(a_2,b_2),(a_3,b_3),... pontok akkor és csak akkor esnek egy origón áthaladó egyenesre, ha (a_1,b_1)^*,(a_2,b_2)^*,(a_3,b_3)^*,... egyenesek párhuzamosak.
* * *
A továbbiakben egy Voronoi-cella, V(P) meghatározását írjuk le.
Koordinátatranszformáció segítségével feltehetjük, hogy P=(0,0). V(P)-t n-1 félsík metszete. Az i-edik félsíkot definiáló egyenes PP_i szakasz felezõmerõlegese (amely szükségszerûen elkerüli az origót): (a_i,b_i)^*. A félsíkok belsejükben tartalmazzák az origót, így egyenletük a_ix+b_iy<= 1.
Egy Voronoi-tartomány meghatározása azt jelenti, hogy az n-1 egyenes közül kiválasztjuk melyek lesznek a tartomány oldalegyenesei és meghatározzuk kerületi sorrendüket.
(i) (a_i,b_i)^* akkor és csak akkor lesz oldalegyenes, ha (a_i,b_i) csúcsa lesz conv{(a_i,b_i): i=1,...,n-1}U{(0,0)}-nek. (ii) (a_i,b_i)^* oldalegyenesek sorrendje a Voronoi-tartomány kerületén azonos a (a_i,b_i) csúcsok sorrendjével conv{(a_i,b_i):i=1,...,n-1}U{(0,0)} kerületén.
Bizonyítás: Csak (i)-t igazoljuk.
Tegyük fel, hogy (a_i,b_i) csúcsa conv{(a_i,b_i):i=1,n-1}-nek. Ekkor van olyan origót elkerülõ (a,b)^* egyenes, amelyre (a_i,b_i) illeszkedik a többi (a_j,b_j) (j/=i) pedig az origóval azonos oldalára esik. A dualitás tulajdonságait felhasználva ekkor van olyan origótól különbözõ (a,b) pont, amelyre az (a_i,b_i)^* egyenes illeszkedik a többi (a_j,b_j)^* (j/=i) egyenesnek pedig az origóval azonos oldalára esik. Tehát az (a_j,b_j)^* (j/=i) egyenesek által határolt félsíkok metszetének (a,b) belsõ pontja. Az összes félsík metszetének pedig kerületi pontja. Így az (a_i,b_i)^* egyenes oldalegyenes. Tegyük fel, hogy (a_i,b_i) nem csúcsa conv{(a_i,b_i):i=1,...,n-1}-nek. Ekkor (a_i,b_i) konvex kombinációja az (a_j,b_j) (j/=i) pontoknak. Így az a_ix+b_iy<= 1 egyenlõtlenség (a konvex kombinációban szereplõ együtthatókkal) kikombinálható az a_jx+b_jy<= 1 (j/=i) egyenlõtlenségbõl. Azaz az a_ix+b_iy<= 1 féltér tartalmazza az a_jx+b_jy<= 1 (j/=i) egyenletû félterek metszetét. Azaz az a_ix+b_iy=1 egyenes nem oldalegyenes.