Voronoi Diagrams

Marchete
10K views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Final words

In this course, we learned the basics of Voronoi Diagrams. The concept is simple yet powerful as Voronoi Diagrams are widely used in many fields.

Pros

  • Simple concept, easy to understand and to apply.
  • Easy to adapt to various problems with customized distance functions.

Cons

  • Voronoi Diagrams can't deal with real-time distances. A planned emergency response diagram renders useless if traffic jams affect ambulances travel time, as you would have to take all these real-time factors into account from your distance function. This would multiply the overall complexity of the algorithm.
  • Resource intensive. Naive implementation is O(n^2) complex. Fortune's algorithm is O(n log(n)) complex.

Codingame Puzzles

CodinGame.com, the online gaming platform for developers, has several puzzles where you can use Voronoi Diagrams:

Many games’ AI make use of Voronoi Diagrams. Some game AI use cases include maximizing controlled area and knowing which resources can be taken faster than the enemy.

Other interesting links

Raymond Hill's Voronoi Implementation

Philippe Rivière The State of D3 Voronoi

Official D3 Voronoi Implementation

Wikipedia: Voronoi Diagram

Wikipedia: Fortune's Algorithm

Wikipedia: Delaunay Triangulation With a hard relationship with Voronoi Diagrams.

References and Credits

This course make use of external resources:

(BSD License Copyright (c) 2015 Mike Bostock)

(MIT License Copyright (c) Philippe Rivière)

(MIT License Copyright (c) 2010-2013 Raymond Hill)

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content