how to generate tessellation cells using the Poincare disk model?

Question

I'm a computer programmer, and while I like math, this is an area where my understanding of math falls short of what I need in order to apply it successfully.

I've been looking at M.C. Escher's "Circle Limit" drawings, which use a Poincare disk model to illustrate tilings of the hyperbolic plane. What I want to do is generate the coordinates (in the Cartesian plane, for a graphics display) of vertices in such a tiling. But I'm not even sure where to start. It seems like I need two things:

1. a way to generate the coordinates in the hyperbolic plane, for each vertex of several cells (polygons) in such a tiling; and
2. the formula to convert those coordinates to the Cartesian plane, using the Poincare Disk model.

For example, in Circle Limit I, each fish seems equivalent to a quadrilateral (four other fish touch its edges), and each vertex is surrounded by either 4 or 6 fish. I don't need to generate fish, just quadrilaterals. But I don't know how to do it.

Do you know of software to do this? Or can someone help me with an algorithm?

I want to generate a finite area of the plane (of course?). If an algorithm could help me generate $k$ rings of cells around the origin, that would be most convenient.

Thanks for any suggestions.

P.S. I'd also be interested in hyperbolic tilings besides Escher's, e.g. http://en.wikipedia.org/wiki/Heptagonal_tiling

P.P.S. I just found some source code for drawing hyperbolic tilings (see bottom of the page), which includes generating locations of vertices. I can extract these vertex coordinates by putting in print statements. But they're grouped by line segment rather than by cell, and converting from the former to the latter does not seem easy.

Answer 1

The most helpful solution I've found for my need -- cranking out the locations of vertices of each polygon -- is David Joyce's Hyperbolic Tessellations applet and its source code. This applet draws regular and quasiregular tessellations organized by polygons, so it's easy to put print statements into the update() method and output the locations of vertices of each polygon as the polygon is drawn. It's much less efficient than Hatch's code, but efficiency is not one of my requirements at this point. Clarity is much more important.

I found the explanations in Ajit Datar's master's thesis the most helpful for learning how the process of generating the tessellations works. There is also code that goes with it, which I have not yet looked at. Datar's program offers more flexibility than Joyce's applet: e.g. Datar's can build tessellations either with a polygon centered at the origin, or with a vertex at the origin; and can also tessellate "motifs" (polygons or polylines such as Escher's fish).

Answer 2

I'm not sure whether this is of any help, but you should note that the lines in these pictures bounding the quadriliterals your are referring to are just (hyperbolic) geodesics. In the disc model of hyperpolic two-space these are precisely (ordinary euclidean) circles (including straight lines) which meet the boundary of the unit disc orthogonally (in the euclidean sense), so from a euclidean point of view it is a rather simple geometrical task to draw such lines and to calculate their intersection points.

(Of course the geodesics are then only those parts of the circles which are lying in the interior of the unit disc).

By googling I found this link which I've chosen randomly from the result list, which explains this and other facts about hyperbolic geometry. It also explains the equivalence between the upper half space and the disc model, which may be useful for you cause I'd expect calculations in the upper half space model to be a little easier (this is just a guess, I do have no experience with this kind of calculation on the computer).

Hth, Thomas

Answer 3

Hop onto Wikipedia, and look up "Möbius Transformations".

If you tile a flat plane with squares, a particular group translations and rotations leaves the pattern unaltered, right? That group is the symmetry group. If you tile the Poincaré circle with whatever, the symmetry group is made up of Möbius transformations.

Or:

On the Poincaré disk, a straight line is a circle that intersects the edge of the disk at right angles. Also, angles are preserved - if two "lines" are at 60 degrees, then they stay at 60 degrees even if you move the focus around. So given a line, a point on the line, and an angle, there's only one circular arc that's a "line".

Or:

Fool with the half-plane model first.