Definíció: A Voronoi-tartományok rendszerét Voronoi-diagramnak nevezzük.
Lemma: Tegyük fel, hogy ponthalmazunk legalább két elemű. Ekkor
(i) Található két olyan Voronoi-tartomány, amely nem diszjunkt.
(ii) A sík minden pontját lefedi valamely Voronoi-tartomány.
(iii) A nyilt Voronoi-tartományok diszjunktak.
(iv) Található olyan pontja a síknak, amely egyik nyilt Voronoi-tartományba se esik bele.
Bizonyítás: (i) és (iv): Ennek igazolásához vegyük a két legközlebbi pontpár ((P,Q)) által meghatározott szakasz felezőpontját, F-et. F a P és Q pont Voronoi-tartományába is beleesik, de egyik nyilt Voronoi-tartománynak sem pontja.
(ii) és (iii) Egyszerű.
Megjegyzés: Az előző órán belátott állítás alapján a Voronoi-tartományok lefedik a síkot úgy, hogy belsejük diszjunkt.
Lemma: Két Voronoi-tartomány
(i) vagy diszjunkt,
(ii) vagy egyetlen közös pontjuk, egy közös csúcspontjuk van,
(iii) vagy egy közös oldaluk van.
Megjegyzés: A fenti lemma állítását röviden úgy mondjuk, hogy a tartományok szabályosan csatlakoznak.
Megjegyzés: A Voronoi-élek mint szakaszok és félegyenesek vagy diszjunktak, vagy diszjunkt belső résszel és közös végponttal rendelkeznek, vagy egybeesnek.
Következmény: (i) Minden Voronoi-él pontosan két Voronoi-tartomány közös éle.
(ii) Minden Voronoi-csúcs legalább három Voronoi-tartomány közös pontja.
Lemma: (i) A Voronoi-tartományok belső pontjai pontosan azok a pontok a síkon, amelyekhez a legközelebbi P-beli pont egyértelmű.
(ii) A Voronoi élek belső pontjai pontosan azok a pontok, amelyek pontosan két P-beli ponthoz esnek legközelebb.
(iii) A Voronoi-csúcsok pontosan azok a pontok, amelyek legalább három P-beli ponthoz esnek legközelebb.
Bizonyitás: Mindhárom állítás azon egyszerű tény következménye, hogy A akkor és csak akkor tartozik V(P)-hez, ha az A-hoz legközelebbi P-beli pontok között ott van P.
Lemma: Azon P-beli pontok, amelyek Voronoi-tartományának van közös csúcsa egy körre esnek.
Következmény: Ha P-ben nincs egy körre illeszkedő négy pont, akkor a Voronoi-csúcsok mindegyikében pontosan három él fut össze.
Megjegyzés: A sztereografikus projekcióval gömbre vetített diagram (az északi pólussal, mint Voronoi-csúccsal kiegészítve) egy gömbre rajzolt gráfot, azaz síkgráfot ad.
Definíció: A fenti síkgráfot Voronoi-gráfnek nevezzük, VG(P)-vel jelöljük.
Lemma: (i) VG(P) pontjainak száma a Voronoi-csúcsok számánál 1-gyel nagyobb érték.
(ii) VG(P) éleinek száma a Voronoi-élek száma. VG(P) tartományainak száma a Voronoi-tartományok száma, |P|=n.
Lemma: (i) VG(P) éleinek száma O(n2).
(ii) VG(P) csúcsainak száma O(n2).
Bizonyítás: Minden Voronoi-tartomány egy legfeljebb n-1 oldallal határolt tartomány. Pontosan n Voronoi-tartomány van.
A továbbiakban ezen becslés élesítését igazoljuk. Belátjuk, hogy az élek és csúcsok száma is O(n).
A Voronoi-élek számának vonatkozó becslés bizonyításának befejezése.
Tétel: Egy G összefüggő, egyszerű síkgráf esetén a tartományok száma: |E(G)|-|V(G)|+2.
Bizonyítás: A Hajós-könyvben lévő bizonyítás vázlata. Nem vizsgaanyag.
Lemma: VG(P) gráf összefüggő.
Következmény: A Voronoi-élek és csúcsok száma O(n).