Legyen P egy síkbeli, n elemű ponthalmaz.
Definíció: A P ponthalmaz egy p pontjának Voronoi-tartománya, V(p;P)=V(p) azon pontok halmaza, amelyek p-től vett távolsága nem nagyobb mint bármelt P-beli ponttól vett távolsága.
Megjegyzés: Ha a síkra mint egy országra gondolunk, a pontok pedig orvosi rendelők, továbbá a közlekedés két pont között a távolsággal arányos időt vesz igénybe, akkor egy pont (orvosi rendelő) Voronoi-tartománya, azok a pontok halmaza, amelyekből a P-be való utazás a leggyorsabb mód egy orvosi rendelő elérésére.
Lemma:
(i) V(p) véges sok zárt féltér metszete.
(ii) V(p)-nek van belső pontja
Megjegyzés: A P ponthalmaz p pontjának nyilt Voronoi-tartománya, V^o(p) azon pontok halmaza, amelyek p-től vett távolsága kisebb mint bármely P-beli ponttól vett távolsága. V^o(p) véges sok nyilt félterek metszete, azaz nyilt. A lemma szerint nem üres. V^o(p) éppen V(p) belsó pontjainka halmaza.
Nézzük meg mit mondhatunk a sík azon tartományairól, amelyek véges sok zárt féltér metszeteként állnak elő?
Tétel: A sík egy véges sok féltér metszeteként előálló tartománya az alábbi lehetőségek közül kerül ki:
(i) az egész sík,
(ii) egy féltér,
(iii) egy sáv,
(iv) egy egyenes,
(v) egy sokszög és egy félegyenes összege (csonkított sáv),
(vi) egy félegyenes,
(vii) egy sokszög és egy szögtartomány (kúp) összege (csonkított kúp),
(viii) egy sokszög,
(ix) egy szakasz,
(x) egy pont,
(xi) üres.
Megjegyzés: A fenti lemma alapján a fenti 11 lehetőség mindent lefed. Ennel több is igaz. A fenti lehetőségek egymást kizárják. Így zárt félterek metszeteként előálló ponthalmaz a fenti 11 típus közül pontosan az egyikhez tartozik oda.
Megjegyzés: A belső pontok halmazának nem üres volta a fenti 11 lehetőség közül meghagyja az alábbiakat mint lehetséges típusok Voronoi-tartományokra: (i), (ii), (iii), (v), (vii) és (viii). Mint látni fogjuk mind a 6 lehetőség elő is áll.
Példa: Ha n=1, akkor az egyetlen pont Voronoi-tartománya az egész sík.
Megjegyzés: A példa mutatja, hogy az (i) típus előáll mint lehetséges Voronoi-tartomány. A példa feltétele megfordítható: Ha ponthalmazunk nem 1 elemű, akkor a Vornoi-tartományok egyike sem a teljes sík. A továbbiakban feltesszük $n=|P|>=2$.
Példa: Egy egyenesre eső, n>=2 pont Voronoi-tartományai.
Lemma: Ha ponthalmazunk egy e egyenesre esik, akkor minden p pontra V(p) tetszőleges q elemével együtt a q-n átmenő e-vel párhuzamos egyenest is tartalmazza. Ez meg is fordítható. Ha egy ponthalmaz bármely p elemének V(p) Voronoi-tartománya tartalmaz egy f egyenest, akkor ponthalmazunk egy f-re merőleges egyenesre esik.
Következmény: Ha egy ponthalmaz egy egyenesre esik és legalább két pontja van, akkor a kialakuló Voronoi-tartományok (ii) és (iii) típusúak, és csak ebben az esetben kapunk ilyen típusú tartományt.
Lemma: Legyen conv P egy szakasz és p a P egy eleme.
(i) V(p) akkor és csak akkor (ii) típusú ha p conv P egy csúcsa.
(ii) V(p) akkor és csak akkor (iii) típusú ha p conv P egy belső pontja.
A továbbiakban feltesszük P pontjai nem esnek egy egyenesre.
A fentiek alapján: Ha conv P egy sokszög akkor a kialakuló Voronoi-tartományok (v), (vii) vagy (viii) típusúak.
Lemma: Tegyük fel, hogy conv P egy sokszög és p a P egy eleme.
(i) V(p) akkor és csak akkor (vii) típusú, ha p conv P egy csúcsa,
(ii) V(p) akkor és csak akkor (v) típusú, ha p conv P egy kerületi pontja, de nem csúcsa (azaz egy oldalszakasz belső pontja),
(iii) V(p) akkor és csak akkor (viii) típusú, ha p conv P egy belső pontja.
Tehát összefoglalva: Ha ponthalmazunk egy elemű (konvex burka egy pont), akkor a Voronoi-tartomány (i) típusú. Ha ponthalmazunk egy egyenesre esik és legalább 2 elemű (konvex burka egy szakasz), akkor a Voronoi-tartományok (ii) és (iii) típusúak. Ha ponthalmazunk nem egy egyenesre esik (konvex burka egy sokszög), akkor a kialakuló Voronoi-tartományok (v), (vii) és (viii) típusúak. Egy p pont esetén V(p) típusát pontosan meghatározza, hogy conv P-hez hogyan viszonyul (csúcsa, oldalának belső pontja, vagy belső pontja).
Példa: Egy szabályos sokszög Voronoi-diagramja.
Példa: Egy egyenlőszárú derékszögű háromszög Voronoi-diagramja és ennek kódolása.
Példa: ``Egy véletlen ponthalmaz'' elemeinek Voronoi-tartományai papíron kiosztva.
A korlátos és nem korlátos Voronoi-tartományok közötti megkülönböztetést kikerülhetjük, ha a Voronoi-diagramot egy sztereografikus projekcióval a gömbre vetítjük. Ekkor a félegyenesek mindegyike a gömb északi sarkába összefut. Így a tartományok mindegyike korlátos, konvex zárt tartomány lesz (a gömbi geometriában).
Az affin modellt is módosíthatjuk ez alapján. A nem korlátos Voronoi-tartományokhoz egy-egy új Voronoi-csúcst adunk, egy végtelen távoli pontot, amely a két félegyenes egy közös végpontja lesz. Így minden Voronoi-tartomány kerülete csúcs-oldal-csúcs-oldal-csúcs-... típusú záródó (körszerűen rendezett) sorozat lesz.
Így egy Voronoi-tartomány kódolása történhet csúcsainak körszerű sorrendjével, illetve a szomszédos csúcspárok által meghatározott oldalegyenesek egyenletének megadásával. Konvex sokszögek kódolásánál a csúcsok körszerű sorrendjét tekintettük csak. EbbőL az oldalegyenesek egyenlete könnyen dekódolható (kiszámolható) volt. A helyzet itt is hasonló, de a végetlen csúcs kivételt alkot: az (x,y) és végtelen csúcs közötti oldal egyenesének egyenlete nems zámolható ki a csúcsok felsorolábólt. Ezeket (két ilyen oldalegyenes van) a kódolás részének kell tekintenünk.