Suppose we have a set of points { p

_{0}, p

_{1}, ..., p

_{n} }, each of which lives in

**R**^{2}. A Voroni Diagram is a partitioning

**R**^{2} 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 ).