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 q₁, and check if that point is closest to p. If it is not, we call the neighbor of q₁ q₂, and check if it is closest. This continues until we find that p is closest to q_n relative to its neighbors Because of the nice properties of the Voroni graph, we can say that q_n 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( n^1/2 ) for 2D ( and more generally O( n^1/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.

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.

The Hough Transform: New and Improved!

  Ok, well it's still not better than a kerneled transform, but I am getting pretty pictures without the use of any trig! To sum up what I'm doing, I'm trying to use python's lambda expressions to generate a function in Cartesian space from the given points. Then I want to run BFGS over that function to find local maxima. By multiplying r = x_0 cos( theta ) + y_0 sin( theta ) through by r and rewriting as x^2 + y^2 = x_0 x + y_0 y , it's easy enough to see that the hough transform of a given point is actually a circle with one point at the origin and centered at \left( \frac{x_0}{2},\frac{y_0}{2}\right).
  This has the nice property that it's easy to calculate the distance between a given line ( point in hough space ) and the nearest point on the circle as a single square root.

I only wish you could dream.

May God us keep From Single vision & Newtons sleep.
—William Blake

   Science is amazing. Think about it, take a look around, and hopefully you'll see what I mean. Heck, don't take a look around. Stare straight at these words on this screen, and realize how incredible it is that we can control electrons to such a degree we can make them take these words from my screen onto yours. It's something almost laughably absurd, it's absolutely ludicrous, but it's reality, the reality we live in because of the generations of scientists who first messed around with amber and cat fur. We owe our modern standard of life to the generations that sought not just to live in, but also to understand the universe and to the people who wrenched every drop out of our collective knowledge and back into the bucket of tools we have to confront and observe the natural world.

Equations Work!

With some help from this post, my blog now supports awesome looking equations (no more blurry bitmaps!). As such, I no longer hesitate to note that E=m c^2 , e^{\pi i}+1=0, and of course that \frac{d}{dx}\int_C^x f(t) dt = f(x) .
Cheers!
Ninjinuity

Note: Equations seem to look best in Firefox. They don't work at all in IE (no surprises there), and they don't quite work in Chrome. I'll keep looking into this. The script also seems to be picking up weird elements of the page and replacing them. I need to stop that.

Edit: The old equations code was inconsistent and had a habit of changing stuff not inside it's tags. With this new back end, they should work everywhere.

Math Puzzler #3

There are six Dudeney numbers, positive integers whose decimal digit sum cubed is equal to the original number. they are
amath 1=1^3=(1)^3 endmath,
amath 512=8^3=(5+1+2)^3 endmath,
amath 4913=17^3=(4+9+1+3)^3 endmath,
amath 5832=18^3=(5+8+3+2)^3 endmath,
amath 17576=26^3=(1+7+5+7+6)^3 endmath,
and amath 19683=27^3=(1+9+6+8+3)^3 amath.

1. Prove there are no larger Dudeney numbers.
2. Find all numbers where the fourth power of the digit sum is equal to the number itself.

Hint: A computer may be useful to check cases, but it is possible to do this problem by hand, albeit with a bit of paper.
Solution 1 after the jump, Solution 2 next week.

Math Puzzler #2

Take a power of two. Rearrange the digits. Can you ever have a second power of two? For simple problem, neglect leading zeros. For a harder one (which I haven't yet solved), don't.

Solutions after the jump.

Life...

...Isn't at it's best right now. I've come down with a nasty crud, and I have a ton of homework to try to get my GPA to a 4.0 before the semester finishes. Luckily I have a break after tomorrow. I'm just gonna ramble for a while, and see if it makes me feel better. Feel free to skip this one.

Professor Stewart's Cabinet of Mathematical Curiosities

This book, written by Professor Ian Stewart, is possibly one of the best books I have ever read. Despite this, it has a format quite unlike an ordinary book; it has no coherent theme, and is full of tricky, and sometimes unsolved, math problems. When I first picked it up, I read the first few problems, and was about to set it down when I decided to flip just a few more pages ahead, and fell upon an essay about Fermat's last theorem.

Cellular Turing Machines(Introduction)

EDIT: I'm going to come back to this project soon and really finish it up, because I think it's worth doing. All my posts are bloated and badly formatted, and I've read up on a lot of relevant material, so I'm going over these with a fine tooth comb and clean them up, post clean code. Basically, I'm going to bring this up to speed, and hopefully release a nice clean application with some features that I really have wanted to see in other programs.

I have known for some time about Conway's game of life, but today I learned two things that surprised me.The first (and less surprising of the two for me) is that the game of life is a Universal Turing machine. In more common terms, it can act as a computer. I guess this doesn't surprise me so much because, in seventh or eighth grade, I remember making something very much like an AND gate in the game of life: Single cell inputs, and a single indicator cell. My gate destroyed itself in computation, but I saw no reason why a stable one could not be constructed (at the time, I was trying to do something other than make a gate, I cannot recall what).

The second, and somehow more surprising discovery (for me at least) was that Conway’s game is not alone. While reading though the book Professor Stewart’s cabinet of mathematical curiosities, I came across a short essay on a mathematical “creature” known as Langton’s Ant. The rules for the ant are simple, arguably simpler than those for the game of life and there is another amazing feature of the ant. Given long enough, the ant always seems to build a “highway” (see the link if you are confused). No one has ever proved this to be true, but no finite configuration of tiles is known that performs otherwise.

Another thing that struck me about the ant: If one imagines the ant to be flipping tiles on a glass plane, then looking at the plane from underneath yield the exact inverse of the view from above. Black tiles are now white, white now black, but the ant obeys the same set of rules. On further investigation of both games, I discovered that even more games exist. Some of these others have similarly interesting properties, like Day & Night, where the inverse of a pattern behaves in exactly the same manner as the original. So anyway, while reading about these various games I had an interesting idea. All the games I have encountered so far are played on a simple grid. As I considered various ways to implement such a grid in a program, one that stood out was a linked data structure, where a node indicated each square, and links showed which squares were adjacent. A second or so later I realized I could construct "loops" from the connections in such a system, and therefore assess the topology to the shape, at least in theory.

For example, most of the games with Langton's ant that I found allowed the ant to roam across the screen, wrapping in both directions as it came to the edge.This describes the topology to a torus: some loops (sets of connections between squares) cannot be "deformed" to a point, in fact, all loops that pass over the edge of the screen cannot be deformed in this manner. If you are confused, try this image, which comes from this page (WARNING: a LOT of math I don't understand EDIT: Oh. Now I do!). The picture shows a grid, which is what is displayed on the screen, and the topological interpretation, a torus. Note that straight lines on the square are circular "loops" on the surface of the torus, and that these loops cannot be moved (imagine rubber bands around a doughnut) in such a way as to squeeze and stretch them down to a point while they remain on the surface.

In any case, I got to thinking about different shapes I could deform the network into, including sphere like shapes, mobius strips (EDIT: I now know I was really thinking of a projective plane here- A kind of double mobius strip that can't be neatly embedded in three space. It's neat. Check it out.), and twisted versions of these shapes (while topology may not care about twists and deformations, the Game of life certainly would), when I had an idea. It will take a while to explain, even on its own, so I will end this post here and pick up the rest later on in another post.Watch for part 2 soon!