Geometric algorithms - Project 1

Voronoi diagram - comparison of construction methods

Introduction

Objective is to divide the Euclidean plane (with set of N points) into N cells (every cell contains exactly one point Pn) in such a way that any random point in given cell is located closer to Pn than to the other N-1 points.

Example diagram

Analyzed algorithms

• Fortune's algorithm (sweep-line approach)
• Bowyer-Watson algorithm (Voronoi diagram is dual to Delaunay triangulation for given set of points)

More details

Detailed description of problem, algorithms, results and conlusion you can find here