On Representing Circles and Disks

JMU is hosting an REU program this summer in computer science. Sarah Ciresi, a rising senior at Georgetown, is working on a project to develop a low-cost 3D scanner for capturing soap bubble configurations. You can follow her progress here.

To aid her work, we’ve been developing a library for inversive geometry on $S^2$ which is (heavily) based on the structure formulated in Sharif Ghali’s excellent book Introduction to Geometric Computing. The goal is to make our library public at the end of the summer.

Ghali covers a lot in his book, including the development of some spherical geometry (though his “circles” are really only the “great circles”), and an implementation of the oriented projective space $T^3$ as formulated in Jorge Stolfi’s PhD thesis and subsequent book. This oriented projective space is really the space of rays in $\mathbb{R}^4$ .

In this post we assume some familiarity with homogeneous coordinates of points in $\mathbb{R}^3$ and their representation in $\mathbb{R}^4$ . Readers unfamiliar with these should check out “Introduction to Geometric Computing” for a very well thought out introduction. (Perhaps we’ll post a video on this sometime.)

Representing disks on the sphere

For our purposes, we needed more spherical geometry than Ghali’s introduction provides. Specifically, we work with circles on $S^2$ which are not necessarily great circles, and we also need our circles to be oriented, meaning that there is a given direction along the circle that is treated as counter-clockwise. Another picture of this is that instead of oriented circles, we are dealing with disks, which are the oriented circles along with the region bounded on the left of the circle (where “left” is defined with respect to the circle’s counter-clockwise orientation).

Now, notice that any circle $C$ on the sphere $S^2$ can be represented by the plane $ax + by + cz + d = 0$ whose intersection with $S^2$ is $C$ . This, in turn, is the intersection of the hyperplane $ax + by + cz + dw = 0$ in $\mathbb{R}^4$ with 3D unit sphere in the the $w=1$ level sub-space. (If it seems like we just jumped into 4-dimensions out of nowhere, don’t worry, it will make sense in a minute.) Thus, we give coordinates to a circle $C$ on $S^2$ by specifying the 4-tuple of coefficients of the hyperplane $(a, b, c, d)$ . Notice that multiplying all the coefficients by any fixed $\lambda$ does not change the circle represented since $ax + by + cz + dw = 0 = \lambda a x + \lambda b y + \lambda c z + \lambda d w$ .

To obtain disks from such a representation, we adopt the convention of Stolfi and treat $(a, b, c, d)$ and $(\lambda a, \lambda b, \lambda c, \lambda d)$ as the same disk if and only if $\lambda > 0$ . Our convention is to identify the disk incident to $C$ with area less than $2\pi$ with those 4-tuples where $d > 0$ and those with area greater than $2\pi$ with those 4-tuples where $d < 0$ . ( $d = 0$ is a great circle, and then the direction of the 3-vector $(a, b, c)$ is used to identify the disk.)

One of the nice things about this representation, is that several computations become trivial. In the following let $(a, b, c, d)$ represent a disk $D$ with boundary $C$ For instance:

The Euclidean center of $C$ (i.e. the center in Euclidean 3-space, not on the sphere $S^2$ ) is given by the homogeneous coordinates $(-a, -b, -c, \sqrt{a^2 + b^2 + c^2} / d)$ , (the 3D point $(\frac{-ad}{L}, \frac{-bd}{L}, \frac{-cd}{L})$ where $L=\sqrt{a^2 + b^2 + c^2}$ ).
The spherical center of $D$ is $(a / L, b / L, c / L)$ where $L$ is defined as above.
The Conical cap of $C$ , which is the apex of the cone tangent to $S^2$ at $C$ is given by the homogeneous coordinates $(-a, -b, -c, d)$ . If $d \neq 0$ , then this corresponds to the 3D point $(-a / d, -b / d, -c / d)$ , and if $d = 0$ , this corresponds to the point at infinite at the endpoint of the ray $(-a, -b, -c)$ . (For the uninitiated, this is the power of the homogeneous coordinates–we can represent points at infinity as if they are any other point. But that is a matter for another post.)

The Inversive Distance

One of the main functions we work with in inversive geometry is the inversive distance between two circles. The usual way of defining this for circles on the sphere is:

$\langle C_{1}, C_{2} \rangle = \frac{-\cos \sphericalangle ( p_{1},p_{2} ) + \cos(r_{1}) \cos(r_{2})}{\sin(r_{1}) \sin(r_{2})}$

where $p_{i}$ is the spherical center of $C_{i}$ and $r_{i}$ is its spherical radius (for $i = 1, 2$ ) and $\cos \sphericalangle ( p_{1},p_{2} )$ is the spherical angle between $p_1$ and $p_2$ .

Given our representation of circles as the 4-tuples $(a_1, b_1, c_1, d_1)$ and $(a_2, b_2, c_2, d_2)$ , the inversive distance becomes

$\langle C_{1}, C_{2} \rangle = \frac{-(a_1 a_2 + b_1 b_2 + c_1 c_2 - d_1 d_2)}{\sqrt{a_1^2 + b_1^2 + c_1^2 - d_1^2} \sqrt{a_2^2 + b_2^2 + c_2^2 - d_2^2}}$

which is simply the $cos(\theta)$ between the vectors $(a_1, b_1, c_1, d_1)$ and $(a_2, b_2, c_2, d_2)$ under the (3,1) Minkowski inner product.

In other words, circles on the sphere endowed with the inversive distance are a geometric picture of vectors in space-time endowed with the usual Minkowski inner product!

Ars Geometrica

The Bowers/Taalman Research Lab in Discrete Geometry

Featured

Image: non-physically-based light transport through bubble cluster