Construction of Voronoi diagrams using Fortune's method : A look on an Implementation

Čuk Roman
Faculty of Electrical Engineering and Computer Science
Laboratory for Computer Graphics and Artificial Intelligence, Center for Geometric Modeling
Smetanova 17, SI-2000 Maribor, SLOVENIA
e-mail: roman.cuk@uni-mb.si, http://www.uni-mb.si/~cgm




Abstract:

The paper deals with an implementation of Voronoi diagrams using Fortune's method. At first, Voronoi diagrams are considered briefly. The idea of Fortune's method is considered then. The implementation details and used data structure are the main focus of the paper.


Keywords: Computational geometry, Voronoi diagram, Fortune's method

1. Introduction
2. Fortune's method
    2.1 Point event
    2.2 Circle event
    2.3 Fortune's algorithm
3. Data structures used in Fortune's method
    3.1 Data structure of Voronoi diagram
    3.2 The data structure for managing the parabolic front
    3.3 Data structure for keeping events
4. Conclusions and future work
5. References

Roman Cuk - roman.cuk@uni-mb.si