:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия »
На правах рекламы
http://cs-quality.ru/download_cs/90-highskill.html
  Построение 2D диаграммы Вороного




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



Cuk 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

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.


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

  Дополнительные материалы:




Построение 2-мерных диаграмм Вороного z i p
Красиво и доступно оформленная презентация на английском, разъясняющая построение диаграммы.