3/11/12

Voroni Diagrams and Graphs I: Introduction

Suppose we have a set of points { p0, p1, ..., pn }, each of which lives in R2. A Voroni Diagram is a partitioning R2 into regions { [p0], [p1], ..., [pn] } so that any point q in [pi] is at least as close to pi as any other pj. Note that, for most points, this should mean that q is strictly closest to pi, 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 { p0, p1, ..., pn }, and whose structure describes the diagram (and provides a quick way to check if q is in a given [pi], among other things ).


To actually find the Voroni Diagram, we'll start by thinking about the boundaries of [pi], a single cell of the diagram.

Imagine we only have two points: pi and pj. In this case, the boundary between [pi] and [pj] is the perpendicular bisector of the segment between pi and pj. 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 pi, then we'll be strictly closer to pi and vice versa.

It follows that [pi] is exactly the closed half plane bounded by the perpendicular bisector between pi and pj. 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 pi: (pi + pj)/2.

If a point q is as close to pas any other p, it must be individually as close to pi as any other specific pj. The converse also holds. While this may seem obvious, it's very important, because it means we can find [pi] by intersecting all the half planes we obtain by considering only pi and each pj individually. We might store the resulting region as the as the series of points { (pi + p0)/2, (pi + p1)/2, ..., (pi + pn)/2 }, the points on the boundary of each half plane closest to pi.


This set of points functions as a complete description of [pi], 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 [pi].



Once we have a method for finding this minimal description of each [pi], it's pretty simple to define the Voroni Graph. The nodes of this undirected graph are { p0, p1, ..., pn }, and there is an edge between pi and pj if and only if (pi + pj)/2 is in the description of [pi].

Equivalently, we could also say that there is an edge between pi and pj if and only if there are at least two distinct points q and r each in both of [pi] and [pj], since this is another way to say that [pi] and [pj] 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 Rand beyond.

No comments:

Post a Comment