Eddig már több olyan algoritmust láttunk, amely mögött egy dinamikus kép állt. Például Jarvish-algoritmus, amelyben egy forgó egyenes járja körül a konvex burkot. Egy másik példa Preparat-Huang Seidel algoritmusa, amleyben egy (függõleges) egyenes seperte végig ponthalmazunkat és az egyenes bal oldalán lévõ pontok konvex burkát (vagy csupán felsõ burkolóját) kiszámítottuk. A seprés végén a kívánt output rendelkezésünkre állt. A dinamikus kép számítógépen nem kezelhetõ (az idõváltozónak kontinuum sok értéken kell áthaladni). Persze nincs is rá szükségünk a folytonosan változó idõparaméternek csupán néhány (véges sok) értéke érdekes. Az idõ nagy részében seprõ egyenesünk csak balról jobbra halad ponthalmazunk elkerülésével, és ilyenkor ``nem történik semmi ''. Az érdekes pillanatok azok, amikor seprõ egyenesünk elér egy új pontot. Ekkor egyenesünk bal oldalára esõ ponthalmaz ``drasztikusan'' megváltozik és ennek megfelelõen a bal oldali pontok konvex burkát újra kell értékelni. Ez a Preparata--Huang-Seidel algoritmus lényege.
A fenti dinamikus kép hangsúlyozását azért végeztük el, mert a Voronoi-diagram meghatározását is így végezzük el. Egy függõleges egyenest mozgatunk balról jobbra. A kiinduló helyzetben összes pontunk a seprõ egyenes jobb oldalára esik. A mozgás minden pillanatában az e egyenestõl balra esõ rész Voronoi-diagramját tudjuk, ez lesz D_b(e).
Nem világos, hogy ez hogyan viszonyul az outputhoz. A seprés alatt új pontok jelennek meg és ezek megváltoztatják az eddig kiszámított képet. A konvex burok esetén ez a változás drasztikus lehet. Az új pont megjelenése a felsõ borkolót egy szakasszá változtathatja, így a korábban kiszámolt esetleg bonyolult felsõ burkoló eldobásra kerülhet. A Voronoi-diagram esetében láthatjuk, hogy D_b(e)-nek egy ``jelentõs része '' már nem fog változni, az outputnak biztos része lesz. Ezt O_b(e)-vel jelöljük. Igazából O_b(e) lesz az amit algoritmusunk folyamatosan tárol és változxásáit számon tartja.
Mik lesznek a dinamikus kép lényeges pontjai? Az világos, hogy amikor seprõ egyenesünk egy új pontot elér, az lényeges pont lesz. Lesz-e más lényeges pont? Kiderül, hogy O_b(e) Kiderül, hogy lesznek.
Atovábbiakban a fenti kérdésekre adunk pontos választ. Hogy a nem központi technikai problémákat elkerüljük feltesszük, hogy pontjaink közül semelyik kettõ által meghatározott egyenes nem lesz függõleges. Továbbá nincs négy pontunk, amely egy körre esne.
Legyen e a seprõ egyenes egy olyan helyzete, amely nem halad át ponthalmazunk egyetlen pontján sem. Legyen D_b(e) az e egyenestõl baloldalra esõ pontok Vornoi-diagramja. Legyen T_b(e) azon pontok mértani helye, amely legalább egy e-tõl balo oldara esõ ponthoz legalább olyan közel vannak, mint e-tõl. Természetesen T_b(e) az e egyenestõl balra esik.
Lemma: T_b(e) véges sok parabolalemez uniója.
Lemma: (i) D_b(e) a T_b(e) tartományba esõ része az e egyenes további (jobbra történõ) mozgása során nem változik. (ii) D_b(e) T_b(e)-n kívül fekvõ része nem szükségszerûen változatlan az e egyenes további mozgása során.
Lemma: T_b(e)-t alkotó parabolalemezeket határoló parabolák nem érintik egymást.
Legyen T_b(e) határán P_1, P_2, ... azon pontok, amelyek több mint egy parabolalemezhez tartoznak. Ezek a pontok a határt parabolaívekre osztják, amelyek pontosan egy parabolához tartoznak. Ezen ívek ``nevét'' írjuk fel. Legyen s az így kapott sorozat.
Lemma: (i) Ebben a sorozatban nincs két egymásutáni karakter, amelyek azonosak. (ii) Nincs négy olyan karakter, amley közül az elsõ és a harmadik azonos, de különbözik a measodik és negyediktõl, amleyek egymás kozött visoznt egyenlõek.
Tétel: Az n karakterbõl alkotott fenti tulajdonságú sorozat legfeljebb 2n-1 hosszú.
Következmény: T_b(e) határa O(n) parabolaívbõl áll.
A ko;vetekzo"kben azt vizsga'ljuk, hogyan va'ltozik O_b(e), illetve T_b(e) hata'ra, ahogy az e egyenest mozgatjuk. Azaz az e egyenes dinamikus mozgata'sa'ban mik lesznek a le'nyeges helyzetek.
Terme'szetesen egy u'j pont ele're'se egy drasztikus va'ltoza'st hoz: A T_b(e)-t definia'lo' parabolalemezek ko;zo;tt egy u'j jelenik meg. Az e egyenes ezen helyzeteit nevezzu;k bizotosan le'nyeges helyzeteknek. Ko;nnyu" meggondolni, hogy a mozgata's sora'n egy ``kicsivel'' az u'j pont mo;ge' e'rve a hozza' tartozo' parabolalemez re'szt is vesz T_b(e) hata'ra'nak kialaki'ta'sa'ban. Ha e_0 azon helyzete egyenesu;nknek, amikor az u'j ponton a'tmegy e's az e_0 egyenesre mero"leges a'lli'tva az u'j pontban az i'gy kapott egyenes T_b(e_0) hgata'ra't egyt parabolai'v belso" pontja'ban metszi,