Suppose we have a set of points { p
0, p
1, ..., p
n }, each of which lives in
R2. A Voroni Diagram is a partitioning
R2 into regions { [p
0], [p
1], ..., [p
n] } so that any point q in [p
i] is at least as close to p
i as any other p
j. Note that, for most points, this should mean that q is strictly closest to p
i, but we're also going to include the boundaries of these regions, so they'll all be closed sets ( If it were to strike your fancy, you could also use open sets. We'll use the closed property a bit later on, but it's mostly personal preference. ).
This is all a perfectly good definition of what Voroni Diagrams are, but it doesn't explain how to find them in practical situations or what they're useful for. In this post, I'll explain a basic approach for finding a Voroni Diagram, and present an (inefficient) algorithm I made up to find what I call the Voroni graph: a graph whose vertices are the { p
0, p
1, ..., p
n }, and whose structure describes the diagram (and provides a quick way to check if q is in a given [p
i], among other things ).
