Voronoi Diagrams

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:

• Tron Battle
• Back to the Code
• Hypersonic
• Ghost in the Cell
• Game of Drones

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:

• Data-Driven Document Library, D3js
• Philippe Rivière The State of D3 Voronoi
• Raymond Hill's implementation of the fortune algorithm

(BSD License Copyright (c) 2015 Mike Bostock)

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

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