Posts by John Bowers

John Bowers is an assistant professor of computer science at James Madison University. His research is in discrete and computational geometry and includes such eclectic areas as origami folding, circle and sphere packing, and polyhedra living in more exotic geometries. When not mathing or teaching, he can be found spending time with his lovely wife and hilarious kids, mountain biking, rock climbing, or playing Overwatch.

November 3, 2017 by John Bowers

Koebe-Lib Initial Release

The initial release of Koebe-Lib, our library for representing constructions in the inversive geometry of circles on the 2-sphere has just been uploaded to GitHub. Currently, the library contains one application, SphericalSketch, which allows a user to define and interact with geometrical objects on the 2-sphere using the python language.

A screenshot of the interface of SphericalSketch is shown above.

July 1, 2017July 3, 2017 by John Bowers

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

This is an image of a non-physically based light transport through a bubble cluster generated as part of REU student Sarah Ciresi’s project. We show a physically based one below as well, but this one just looked too cool not post. This image was produced after we added circular arc rendering to a 2D raytracer, but before we added the actual simulation of light through a thin soapy film. We hope you’ll allow us some artistic license even though we’re mucking around with the physics:

The bubble cluster was generated using our Koebe-Lib library for inversive geometry that we have developed over the past two months. The light transport was simulated with a modified version of Tantalum, a nice GPU-based 2D raytracer designed to simulate physically modeled light transport through a scene.

Here’s a rendering that is more accurately modeling the physics of light passing through a thin-film. Not quite as visually stunning, but still pretty cool:

The light source is modeled as an incandescent light. We used 1.0 for the index of refraction of air and 1.33 for the index of refraction of soapy water. We are not currently simulating any color shift on reflected rays, but may add this in the future. Our walls are also modeled as infinitesimally thick, since the thickness of a bubble wall at this resolution is much smaller than a pixel. The scene was rendered using 12 million simulated photons.

Stay tuned for an initial release of Koebe-Lib’s alpha version, which we expect will occur within the next month.

May 26, 2017July 3, 2017 by John Bowers

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!

April 6, 2017June 5, 2017 by John Bowers

New Paper: Rigidity of Circle Polyhedra in the 2-Sphere and of Hyperideal Polyhedra in Hyperbolic 3-Space

We just posted a new paper to the ArXiV, “Rigidity of Circle Polyhedra in the 2-Sphere and of Hyperideal Polyhedra in Hyperbolic 3-Space“. This is joint work with Philip L. Bowers at FSU and Kevin Pratt, who worked on the project over the summer as a visiting undergraduate research assistant here at JMU.

This paper grew out of the curious and surprising result of Jiming Ma and Jean-Marc Schlenker, in which they construct an inversive distance circle packing on the sphere which is not globally rigid (meaning that there exist more than one realization of the same inversive distance data as a pattern of circles that are not Möbius equivalent).

Suppose you are given a triangulation $K$ of a topological sphere and a real number weight $w(ij)$ on each edge $ij$ of $K$ . The inversive distance circle packing problem asks, is there a set of circles $C$ on the sphere and a bijection $P : V(K) \rightarrow C$ such that for every edge $ij$ of $K$ , the inversive distance between circles $P(i)$ and $P(j)$ is equal to the weight $w(ij)$ ? We call $C$ an inversive distance circle packing realizing $(K, w)$ . There are really two important questions: (1) given such a $K$ and edge labeling $w$ , does there exist a packing? and (2) if one does exist, is it unique?

The Ma-Schlenker result was especially surprising because the answer to question (2) has been yes, it’s unique, in virtually every setting circle packings have been studied. (As of this post’s writing, question (1) remains very much open for general inversive distance circle packings.) Ma and Schlenker start with a Euclidean twisted octahedron and use some powerful mathematical tools (Pogorolov maps and infinite de Sitter space) to obtain their result. Recently, we provided some constructions of Ma-Schlenker style octahedra in the intrinsic inversive geometry of the sphere in another paper that may interest the reader. We can now construct lots of examples of families of circle-polyhedra where there is not uniqueness.

The Ma-Schlenker construction raises the question, “When is global rigidity of an inversive distance circle pattern on the sphere guaranteed?” This is the subject of our paper.

Enter Cauchy

The questions being asked of circle patterns have an analog in the study of Euclidean polyhedra dating back to the ancient Greeks. The question might be asked, if we know the shapes of all the faces of a polyhedron and which faces are attached together along which edges (though not at what dihedral angle), does that data determine the polyhedron uniquely? In general, the answer is no–take a cube and replace its top face with a pyramid made of four equilateral triangles to obtain a house-like structure; now, invert the pyramid. However, in 1813, Cauchy proved his celebrated Rigidity Theorem, which states that if we further require that the polyhedron be convex, along with the specified faces and their combinatorics, then there is only one construction possible. This theorem (and some of its later proofs–Cauchy’s original argument had several serious bugs) is certainly one of Erdös’s proofs from the book (and in fact one proof of the theorem is in the Aigner and Ziegler book Proofs from THE BOOK).

To Our Paper

Inspired by Ma and Schlenker’s use of Euclidean polyhedra to prove their result, we set out to recreate Cauchy’s proof, except in the case of inversive distance circle packings. To do this, we first generalized packings to circle-polyhedra, which are really the natural way of talking about gluing up circle-polygons along “edges” to form patterns of circles on the sphere. In order to do this, we began to work with circle space, a space that is a partial dual to the real-projective 3-space in which circles are points, coaxial families of circles are lines, and bundles of circles are planes. Along with this space comes a notion of convexity for circle-polyhedra, and our main result is an analog to Cauchy’s: if you specify (up to Möbius transformations) a bunch of circle-polygons (to serve as the faces of a polyhedron), and how the polygons should be combined (by identifying edges), then if there exists a convex circle-polyhedron satisfying your specifications, it is the unique convex circle-polyhedron satisfying your specifications.

Our proof of this theorem follows the same general outline as Cauchy’s original proof, though with some really lovely forays into hyperbolic geometry. (A quick preview: if a bunch of circles intersect some other circle orthogonally, we can take the parts of each of the intersecting circles lying on the interior of the one circle to be hyperbolic lines in the Poincare disk model of hyperbolic 2-space. From there we build some nice hyperbolic polygons with some interesting properties, and derive a lemma about certain hyperbolic robot arms constructed out of revolute joints with the occasional piston thrown in. It’s all very fun.)

Check out the full details here.

February 23, 2017February 23, 2017 by John Bowers

We’ve acquired a 3D printer!

We’ve acquired a 3D printer! Already I’m learning that this is a far from automated process. Here’s the printer, a FlashForge Creator Pro with a print of a twisted pen-holder I coded in OpenSCAD:

A good third print.

Here’s a successful print of a 3D graph filling the interior of a Pikachu model. The code for computing this graph is using our circle and sphere packing heuristics to generate a volume filling tetrahedral graph that is a sub-graph of the cannonball lattice:

Pikachu, I choose you!

I tried to print a much thinner version of Pikachu, but it wasn’t working that well:

When prints go awry.

The lab is a lot more hands-on these days than theoreticians normally get to go =D. Here’s one final print to start things off right:

Ars Geometrica

The Bowers/Taalman Research Lab in Discrete Geometry

Featured

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

On Representing Circles and Disks

Student Post: Sphere Packing Honors Thesis Proposal

New Paper: Rigidity of Circle Polyhedra in the 2-Sphere and of Hyperideal Polyhedra in Hyperbolic 3-Space

Author / John Bowers

Posts by John Bowers

Koebe-Lib Initial Release

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

On Representing Circles and Disks

Representing disks on the sphere

The Inversive Distance

New Paper: Rigidity of Circle Polyhedra in the 2-Sphere and of Hyperideal Polyhedra in Hyperbolic 3-Space

We’ve acquired a 3D printer!