Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Category Archives: geometry

138: Projected Circles on the Reimann Sphere

Under the Reimann Sphere projection, circles on the sphere are mapped to “circles” in the extended complex plane \mathbb{C}^*.

The quotes are because every line in \mathbb{C}^* is mapped to by a circle on the Reimann Sphere passing through the north pole \mathcal{N}. So in this view, lines in \mathbb{C} are just circles in \mathbb{C}^*.

Advertisements

120: Z Order

Z order is a map between 1-dimensional and n-dimensional space which does a decent job of preserving locality (“closeness” between points).

The calculation of Z order from 1 to 2 dimensions is extremely straightforward. Select 4^k points from a 1-dimensional interval, and index them according to order in the obvious way using binary. If working with 64 points for instance, with k=3, they’d be labeled 000000, 000001, 000010, …, 111110, 111111. Then recursively split your 2-dimensional square into subsquares k times. Again with k=3, you’d have 64 subsquares.

Now given a binary index for a point, read 2 digits at a time, from left to right. If the two digits read are 00, direct the point into the upper-left quadrant. If 01, upper-right. If 10, lower-left. If 11, lower-right. Go on reading the index 2 digits at a time, recursively directing the point into subsquares until you reach the end of the index, and then that subsquare is where the point goes.

A picture, to make this more clear (courtesy of David Eppstein):

z order.png

I recommend ignoring the stuff in the margins; just look at the labels for points and where they end up.

Here’s what the result of this map looks like for k = 1, 2, 3, 4:

z ord

The inverse map from 2D to 1D is obvious.

118: Clustering in the Hilbert Curve

The Hilbert map between 1-dimensional and 2-dimensional space has the nice property that distances between points in 1D space are (relatively) preserved when those points are mapped into 2D space. Informally, if 2 points are close together on a line segment then they will also be close together when that segment is transformed into a Hilbert curve.

The converse is not always true, but is in some cases.

This property is illustrated in the picture below, which is the result of mapping the color spectrum into a square using the Hilbert mapping (image courtesy of Jason Davies):

hilbertcolors

Because of this nice locality property, the Hilbert curve lends itself to many applications in computer science. For instance, if one wants to index multi-dimensional data in a way that indices preserve the distance between datapoints, a multi-dimensional Hilbert mapping can be used. (The Hilbert curve has generalizations beyond just 2 dimensions.)

90: The Standard (Unit) Simplex

The standard n-simplex, sometimes denoted \Delta^n, is the n-simplex in \mathbb{R}^{n + 1} with its vertices at the n + 1 ‘unit’ points

e_0 = (1, 0, 0, \dots, 0)

e_1 = (0, 1, 0, \dots, 0)

e_2 = (0, 0, 1, \dots, 0)

\dots

e_n = (0, 0, 0, \dots, 1).

For example, \Delta ^0 is the point 1 in \mathbb{R}^1\Delta ^1 is the line segment from (0, 1) to (1, 0) in \mathbb{R}^2, and so on. A formal description is

\Delta ^n = \{(x_0, x_1, \dots, x_n) \in \mathbb{R}^{n+1} | \sum _{i = 0} ^{n} x_i = 1, x_i \geq 0 \}.

One possible interpretation of \Delta ^n is as the set of possible probability distributions of a categorical distribution on n+1 variables.