Emne: Voronoi diagram
Tekst: Chapter 7, fra "Computational Geometry "
Kopier er i kursets boks.

Kik endvidere paa foelgende opgave. Lad P vaere n punkter i planen. Der er givet en algoritme som bruger O(n log n) tid paa preprocessering, saaledes at man on-line derefter i O(log n) tid kan finde et punkt fra P som er taettest paa et vilkaarligt punkt i planen.

Konstruer en algoritme som understoetter operationer der kan indsaette og slette punkter i planen, samt for et givet punkt x i planen returnere et af de indsatte punkter som er taettest paa dette punkt x. Algoritme skal bruge o(n log n) tid per operation.

Obligatorisk opgave. Voronoi diagram i traer. Lad der være givet et trae med n knuder.
Af de n knuder er de k knuder markeret.
De markeret knuder, er markeret med et unikt tal mellem 1 og k.
Afstand mellem to knuder i traet er antallet af kanter paa den unikke vej mellem dem.
Konstruer en algoritme som skriver en værdi i alle knuderne. Hvis en knude x har værdien "j", skal en hver afstand fra x til en af de markeret knuder være lig med eller størrer end afstanden fra x til "j".
Algoritmen skal køre i O(n) tid.