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 { p₀, p₁, ..., p_n }, each of which lives in R². A Voroni Diagram is a partitioning R² into regions { [p₀], [p₁], ..., [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₀, p₁, ..., 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 ).

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.