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.