Diagramy Voronoia

Motivace - post office problem. Matematicky: pro danou množinu P bodů v rovině najít podrozdělení roviny na oblasti tvořené body, které mají nejblíže k danému bodu množiny P. Výsledné podrozdělení se nazývá digramem Voronoia. Odhad na počet vrcholů a hran tohoto digramu. Charakterizace hran a vrcholů diagramu Voronoia pomocí kružnic. Algoritmus konstrukce pomocí pročesávací přímky. Beach line tvořená oblouky parabol. Kdy v beach line vzniká nový oblouk - site event. Kdy v beach line nějaký oblouk zaniká-circle event (kruhová událost). 

Datová struktura: fronta událostí (site a circle events), kruhové události jsou do fronty doplňovány až v průběhu algoritmu. Vyvážený binární strom T uchovává pořadí oblouků parabol. K každém listu je případný odkaz na kruhový bod, kdy oblouk zanikne. Algoritmy V-DIAGRAM, HANDLE SITE EVENT a HANDLE CIRCLE EVENT


 

Blackboards