Voroni Diagrams and Graphs IV: Efficient Computation of the Graph and it's simplexes.

Before we jump into algorithms, a few things. The algorithm I'm about to lay out is a version of the Bowyer-Watson algorithm I've referenced in a previous post. It's been pretty heavily modified since, and it was not my initial intent for it to be thins similar. Nonetheless, I think that my implementation has better asymptotic time than any implementation of the original I've yet seen, since (as we'll see) the most intensive parts of the algorithm (most of which were related to searches over the point set) have been offloaded to a simple graph search. We'll also be looking at things through the lens of the Voroni Graph, rather than the Delaunay Triangulation.


A Simple 2D Graphics Engine Powered by OpenGL/GLUT.

In the course of coding up my ideas on the Voroni Graph, it became apparent that a CLI wasn't going to cut it. I needed some sort of graphical library, both for the final visualization, and for debugging. For this, I've chosen to use OpenGL with my own wrappers on top. This is a log of what I've been working on for the past few evenings.

This is, without the slightest doubt, overkill for what I'm doing right now (2D, very few colors, order of 100 different positions.). Screw that, I'm using OpenGL anyways. Why? I want the experience, and I want to write my own graphics engines that won't be limited by the underlying platform.

In any case, the process of getting to where I am now has been fairly frustrating. The documentation for all sorts of things involving OpenGL on the web is scant and often contradictory. Some things didn't work, other important aspects of a simple program had been depreciated. Getting even a blank screen to compile was a significant achievement.

In any case, this was all difficult enough to warrant a post and some preliminary code. Below is a sort of black box on the whole process, written as I worked through everything. For this reason, please excuse the weird tenses.


Prelude and Fugue

There's a long story behind these: Basically, they were written for me in about 10 minutes during orientation after an off comment that I played the cello. Yes this is in pen (though I did enhance the contrast). Hit the break to see scans...


Voroni Diagrams and Graphs III: The Dual.

In this post, I'll write about the geometric significance of the dual of the Voroni graph and try to convince you that we can extend our discussion, which has so far focused on two dimensions, up to three-dimensions with only some minor changes ( I'll conjecture that the relationships I'm about to lay out extend much beyond that, but I don't have much proof of this ).

First, though, we need to discuss what a dual is.

The dual of a graph is itself another graph. Basically every face in the graph is a node in the dual, and two nodes in the dual have an edge between them if ( and only if ) their two corresponding faces share an edge (corners don't count).

The dual of a planar graph is itself a planar graph, and I claim that the dual of the dual of a graph is the graph itself (with the caveat that we discuss in the next paragraph). The figure below hints at a proof for this (note the crossing edges), though I'm not going to formalize it.


Voroni Diagrams and Graphs II: Some Applications of the Voroni Graph.

In this post, I'll further discuss the concept of the Voroni graph we talked about last time, and talk about some uses. We'll see more uses in the next post, where I'll talk a bit about a related graph.

Supposing we know the Voroni Graph of a set of points, what can we do with it?

First, we can use it to check if a point p is in the Voroni cell of some point in our set q. If we find all the neighbors of q ( points that have an edge to q in the Voroni Graph ) we only have to check to make sure that p is closer to q than any of these points, since we already know that these neighbors alone are sufficient to define the cell of q.

Let's briefly look at how much of an improvement this is over a normal check. Let's assume we have a set of n randomly distributed points, and n is very large (AKA we can neglect the effects of the outermost border of the points, and we're not going to get anything unusual in our graph).

If we have to check each point to see if p is closest to q, then we'll take O(n) time. This isn't bad, but if we assume we have access to the Voroni graph, we can do much better.

We need to find how many neighbors a typical Voroni diagram has.We know that the Voroni graph is planar, so it will obey Euler's formula ( V − E + F = 2 ). If the points are fairly random, then almost all of the "faces" of the graph will be triangles ( A non triangular face, we'll see later, implies that at least four of the points lie on a single circle, which is in general not true. ). Because of this F = 2E / 3 ( each triangle is bounded by three edges, and each edge divides two triangles ).

V - E + (2/3) E = 2
V - 2 = (1/3) E
E/V = 3 - 6 / V
2E/V = 6 - 12 / V

The quantity 2E/V represents the average number of neighbors of each vertex (we double the number of edges so that both ends can count it). Thus, as the number of vertices becomes large, each vertex will have on average only 6 neighbors. Thus, if we can use the Voroni Graph, we can check our point in only O(1) time!

It's worth noting of course, that this isn't quite as good as it seems. After all, we still have to compute the Voroni Graph, and we'll need to store it in such a way as to allow ourselves to look up a given vertex quickly. Still, it's an achievement, and it lets us know that if we're going to be checking lots of points, we'd be better off investing our time in making the Voroni graph rather than brute forcing the problem.

Even better, because p is in the cell of q if and only if it is closer to q than q's neighbors, it is also painless to find out which point is closest to p. We simply pick a starting point q1, and check if that point is closest to p. If it is not, we call the neighbor of q1 q2, and check if it is closest. This continues until we find that p is closest to qn relative to its neighbors Because of the nice properties of the Voroni graph, we can say that qn will be the point in our point set which is closest to p. In other words, having the Voroni graph lets us do a greedy search to find the Voroni cell to which a point belongs.

I would love to analyse the run-time of this particular algorithm, given a large set of points and a randomly chosen starting point, but I must confess I am not clever enough to put down any of my thoughts on paper at this point. I'll continue to think on it, but my money is on O( n1/2 ) for 2D ( and more generally O( n1/d ) for dimension d ). I think this is how the average euclidean distance between two randomly selected points scales as the number of points increases.

In any case, it is a great improvement over the naive approach, which would require us to check the distance to every point, and thus would have O( n ) run-time.

That's it for this post. I've got two more queued up and ready to go as soon as I have time to edit them and add figures, so expect more on this topic soon.


The Hough Transform I: Finding Lines

I've made reference to the Hough Transform in several previous posts, but I haven't ever done posts on what the transform is in a general sense, and how I've used it (and tried to improve it) in the past. In this series of posts, I'll try to rectify that.

The most basic implementation of the Hough transform is used to find lines in an edge image like the one below.  In this post I'll walk through the basic process of using the Hough transform to find lines in this image.
An image of machinery with edge detection applied. This image would be a good candidate for further processing with the Hough transform. (Source: Wikipedia)
Underlying the Hough transform is the idea that each pixel in an an image tells us something about the chances of there being certain lines in the entire image. If we have a pixel at point p, then it would make sense to look at all the lines that pass through p, and see if any of them happen to pass very close many other points in the image. If a particular line through p passes close to an unusual number of points, then it's a pretty reasonable to assume that this line constitutes an actual feature in the image.


MIT Library Scanning...

...turns out to be a great way to scan figures. It's a ton faster than using my own scanner, and the resolution isn't too much worse. I'm writing a few math-oriented and cs-oriented posts with figures right now, and the book scanner means I can just box figures in my notebooks and use Gimp / Picasa Web Albums to crop things down and clear up the colors. It's a much faster pipeline than what I had before, and I'll hopefully make use of it to put lots of pretty figures in my posts.


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 ).


Quaternions I: Overview

What are quaternions? Let's start with what quaternions once were: an attempt to extend Complex numbers to three dimensions.

Back when the geometric interpretation of complex numbers as a plane was reasonably fresh, Sir William Hamilton became interested in finding a system of algebra that would allow him to express three dimensional space in the same way. To do this, Hamilton needed a way to add and multiply points in 3 dimensional space together.

Addition came easy. Picking some arbitrary origin and axes 1, i, and j to work with, Hamilton just defined (a + bi +cj) + (d + ei +fj ) = ( a + d ) + ( b + e )i + ( c  + f )j.

Multiplication, though, was a problem. Assuming that these new quantities were distributive, Hamilton needed to define ij in such a way that various other properties still held. Despite his best efforts, he couldn't do it.