3 Points Make a Circle

While learning about Voronoi diagrams from Computational Geometry, I had trouble justifying a single statement from a proof regarding the complexity ( as a function of $n$ sites ) of Voronoi diagrams. For completeness I’ll restate the theorem here.

Theorem. For $n \geq 3$, the number of vertices in the Voronoi diagram of a set of $n$ point sites in the plane is at most $2n-5$ and the number of edges is at most $3n-6$.

To establish the stated bounds, the proof hinges on the constancy of the Euler’s characteristic of graphs (that embed in $S^2$) and every vertex in the Voronoi diagram has degree at least three. Really? At the point in the proof when this fact is invoked we know that all the $n$ sites are not colinear; so given any pair of sites there’s a third site that does not lie on the line passing through them. Three points induce a vertex. But why?? Voronoi vertices have a specific meaning/interpretation; they are equidistant from sites, which means that a Voronoi vertex is the center of circle that passes through at least three sites.

Which to me begs the question: Is it possible to find a circle that passes through any three non-colinear points in the plane?

Well it’s true. Up to rotation and scaling the three given points can be positioned like

helpful graphic

Draw imaginary lines bisecting the edges $AB$ and $BC$. Because our points form a proper triangle, these bisectors intersect.

helpful graphic

Voila! The intersection of the two bisectors is the center of a circle which passes through $A, B,C$.

helpful graphic

Functional Prime Number Sieve

In a post a few years ago I discussed primality testing. For some reason I thought I described the basic prime number sieve (I’m pretty sure there is only one) there, but apparently I didn’t. No worries. The prime number sieve solves a different problem; that of generating a list of the first $N$ primes. One could use a primality testing method to do this as well; namely filter a list of numbers with the primality test as a predicate; but sieve based methods are faster and conceptually much easier.

The prime number sieve iteratively filters out all the composite numbers, with the caveat that the leading number in the input is a prime. For , we put aside $2$, the smallest number, and filter out all multiples of $2$; then put aside $3$ and filter out multiples of $3$, and so on. This process, shown below as a decreasing sequence, terminates with a set of primes.

At each stage we have a list of some primes and a residual set, which if it is nonempty must be filtered; this process terminates when the residual set is empty. Filtering and subsequent residuals sort of defines the set of all primes; however it is an infinite process.

When $n$ primes have been filtered the state looks like . Here we denote the residual set $A_{p_i}$ where $p_i$ is the leading/smallest number of the residual set. Consecutive residuals are related by

Anyone schooled in imperative programming ( which I guess is most of the world ;)) would go about implementing a function which returns the first $N$ primes by iteratively filtering and collecting primes in a loop. I should emphasize that when I write iteratively, I mean that the instructions for filtering and collecting primes are done eagerly.

Putting aside the computation for the first $N$ primes, all primes ( which is an infinite set ) can be expressed as a mathematical set, without really specifying how to compute the next prime.

Okay, the second set from above is practically a tautology…but I digress. The point here is that in mathematical notation we are free to declare an expression for the set all primes, even if there is no set notation for it. Generally in mathematics it’s common to express and manipulate infinite sequences and series. Being somewhat aware of Haskell’s declarative nature, I wondered at the outset if I could create an expression for all primes and subsequently generate finite lists of primes as needed. As you might guess the answer is Yes :)

For the uninitiated, referencing Haskell may seem like a non sequitur. Haskell codes are composed of expressions, which are meant to be true statements, as opposed to instructions for the computer to execute in sequence. Expressions in a Haskell program ( or any pure functional language for that matter) are executed as needed, lazily. As opposed to eagerly. Computing the set of all primes via the iterative/imperative prime number sieve implementation would be an infinite loop. Which would never end… And that’s the key difference: declaring/expressing the set of all primes versus computing all primes.

We can easily adapt the sieve described earlier. Haskell is nothing if not functional, so we define the following function,

I first tried to explicitly iterate through a finite list of consecutive numbers; as I was developing I was trying to get a feel for haskell. But I couldn’t see how to generate the whole collection; and doing an infinite loop seemed wrong somehow–the idea of finding the analog of generators in haskell hadn’t occurred to me. Also, probably not idiomatic haskell anyway.

The proper way to express all primes is to recurse, by calling $f$, within its definition, on the residual set. This elegant solution is actually shown ( at the time of this post was written ) on the upper right of the haskell.org landing page. Let , then

When $S$ is infinite, the $RHS$ is also infinite. However the infinite recursion is never realized because of lazy evaluation. In particular the set of all primes is expressed by . To me this recursive definition is a sort of set builder notation. The listing below is the Haskell implementation of $f$, declaration of all primes, and a request for a finite subset of $primes$.

Prelude> filterPrime (p:xs) = p : filterPrime [x | x <- xs, (mod x p) /= 0]
Prelude> primes = filterPrime [2..]
Prelude> take 30 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]

Losing My Orientation

While trying to grok $SO(3) \cong \mathbb{RP}^3$ and understand various parametrizations of $SO(3)$, I wandered a bit (okay maybe more that litte:) ) and started to think about projective space itself. It is well know that real projective spaces alternate between being orientable and non-orientable, as dimension increases. Specifically odd dimensional projective spaces are orientable but even ones are not. For example, $\mathbb{RP}^1$ and $\mathbb{RP}^3$ are orientable but $\mathbb{RP}^2$ is not.

Jeffery Week’s Space of Space gives a Flatland inspired explanation of orientations on the projective plane and projective 3-space. It’s a fantastic book and a wonderful example of storytelling as a teaching method. In this note, I want to invoke Week’s style and describe orientations on real projective spaces of any dimension.

Lets start with a low dimensional example, $\mathbb{RP}^2$. There are a few ways to describe the real projective plane: affine plane with points at infinity, as a sphere with antipodes identified, or a disc with boundary antipodes identified. We can’t embed $\mathbb{RP}^2$ in 3-dimensional space so we’re forced to work with patches. So, the disc model will serve our purposes best.

Suppose Pac-Man lives on the real projective plane. He’s hungry and sees food down the road. The boundary of the disc is identified, albeit in a reverse oriented way (note the arrows), so Pac-Man sees no obstruction.

Pac-Man normal

What does Pac-Man look like when he crosses the disc boundary?

Antipodal identification means that as Pac-Man crosses the boundary of the disc, he is flipped about his midline. As he emerges from the left side he appears flipped with his left side in view. Of course in 2-dimensional space there is no sidedness, but we can excise the road with Pac-Man ( after all it is just a Möbius Band! ) and embed it in 3-dimensional space to help us visualize Pac-Man’s journey. Another way to think about it without appealing to a 3-dimensional embedding is to imagine Pac-Man passing through the boundary one vertical strip at a time. Each time a strip hits the boundary it is up-down reversed and then sent to the opposite side. I imagine him emerging from the left side like a image being printed by a dot matrix printer. Each passage of the print head depositing a up-down reversed strip of Pac-Man.

Pac-Man mirror reversed

The question remains: Is Pac-Man differently oriented? Imagine an arrow curving the clockwise direction on Pac-Man’s face prior to his passage through the boundary of the disc. That curving arrow is in the counterclockwise direction when he appears from the left; which, to me is a succinct demonstration that Pac-Man’s orientation is reversed.

…So then what is orientation? Well, we’ve seen that Pac-Man is reverse oriented because he’s flipped, once. That could be a definition: one flip. What about two or three, etc.? The boundary identification induces a motion on Pac-Man that leaves his form and shape unchanged. These motions are described by orthogonal groups for continuous objects, like Pac-Man. Though for a more concrete explanation imagine a polygon in 2-dimensions and we only care about how it is rearranged by the topology of the space. These symmetries are described exactly by Dihedral groups; which are composed of flips (reflections) and rotations. It should be clear that rotations are orientation preserving – a clockwise motion rotated remains clockwise. A flip followed by another flip is always a rotation, and rotations form a group. So, we have an answer: an even # of flips preserves orientation, while an odd # of flips reverses orientation.

Lets apply this definition to determine the orientation of $\mathbb{RP}^n$ where $n$ is $3$ or more. We can model $\mathbb{RP}^n$ as a $n$-ball with the boundary antipodally identified. Imagine a boxy Pac-Man floating over a road in $B^n$. Again he sees no boundary because of the identification, nonetheless as he passes through he will be altered somehow.

3D Pac-Man

Lets consider $n-1$ dimensional slices of Pac-Man, since the boundary of the ball is a $n-1$-sphere and we can think of Pac-Man passing through the boundary slice by slice. We can imagine the boundary, when viewed heuristically from a $n-1$-dimensional slice, drawn below, as the inside of a sphere. The horizontal axis representing $n-2$ directions and the vertical axis one direction.

slice view

Each slice is flipped $1 + # { flips in n-2 directions}$ times; a recursive relation–for simplicity let $n$ replace $n-1$; $n$ matches the dimension of the real projective space of interest.

Orientation is the parity of $f$, so $n-1 \mod 2$ represents orientation. So 3D Pac-Man’s orientation in $\mathbb{RP}^3$ is preserved! And in general