_{0}, p

_{1}, ..., p

_{n}}, each of which lives in

**R**. A Voroni Diagram is a partitioning

^{2}**R**into regions { [p

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

To actually find the Voroni Diagram, we'll start by thinking about the boundaries of [p

_{i}], a single cell of the diagram.

Imagine we only have two points: p

_{i}and p

_{j}. In this case, the boundary between [p

_{i}] and [pj] is the perpendicular bisector of the segment between p

_{i}and p

_{j}. Why? Each point on the bisector is equidistant from the two points. By our definitions, that means that each one of these points belongs in both cells. Furthermore, if we move off this line, then we know that we'll be strictly closer to one point or the either. If we move off the bisector in the direction of p

_{i}, then we'll be strictly closer to p

_{i}and vice versa.

It follows that [p

_{i}] is exactly the closed half plane bounded by the perpendicular bisector between p

_{i}and p

_{j}. It's worth noting at this point that a very convenient way to store this line is just the point on the line closest to p

_{i}: (p

_{i}+ p

_{j})/2.

If a point q is as close to p

_{i }as any other p, it must be individually as close to p

_{i}as any other specific p

_{j}. The converse also holds. While this may seem obvious, it's very important, because it means we can find [p

_{i}] by intersecting all the half planes we obtain by considering only p

_{i}and each p

_{j}individually. We might store the resulting region as the as the series of points { (p

_{i}+ p

_{0})/2, (p

_{i}+ p1)/2, ..., (p

_{i}+ pn)/2 }, the points on the boundary of each half plane closest to p

_{i}.

This set of points functions as a complete description of [p

_{i}], but it's not the smallest description. To get that, we'll need to check that we don't have unused or redundant borders. If one closest point is not in the (open) half plane of both of two other points, then there's no way it can effect the final shape, so we can discard it. If we use this process to remove redundant points, then we'll have a compact description of [p

_{i}].

Once we have a method for finding this minimal description of each [p

_{i}], it's pretty simple to define the Voroni Graph. The nodes of this undirected graph are { p

_{0}, p

_{1}, ..., p

_{n}}, and there is an edge between p

_{i}and p

_{j}if and only if (p

_{i}+ pj)/2 is in the description of [p

_{i}].

Equivalently, we could also say that there is an edge between p

_{i}and p

_{j}if and only if there are at least two distinct points q and r each in both of [p

_{i}] and [p

_{j}], since this is another way to say that [p

_{i}] and [p

_{j}] share a border. There's a little bit of math involved in showing that having two points really is the same as sharing a line segment border. If you're interested or skeptical, try proving that Voroni regions are all convex.

That's it! This is a functional definition of the Voroni Graph both mathematically and practically speaking. Later on, we're refine our process for finding this graph, but the basic idea is complete.

I'll touch this post up with pictures some time soon. In the next two posts on this subject, I'll first describe some more math surrounding the Voroni Graph. Finally, we'll revisit the process of finding a Voroni Graph, and generalize it to

**R**and beyond.

^{n }
## No comments:

## Post a Comment