reveal.js

Raster methods

Imaging Holomorphic dynamics
& Kleinian groups

Ad: https://www.math.u-bordeaux.fr/wiki-klein/

Imagine you want to draw a hyperbolic tesselation in the Poincaré disk model.

Say the {3,7} tesselation:
equilateral triangles, 7 per vertex.

Draw disk
Draw appropriate arcs of geodesics
They are all image of one arc by a group of (direct) isometries

The {3,7} tesselation group is generated by an order 3 rotation a and an order 7 rotation b. They do not commute but are not independent either.

Variant: considering a reflection group (Coxeter). The discussion would be very similar.

A naive but not so bad approach consists in ignoring all the relations in the group and iterate over the tree of possibilities:

def recursion(S,prev,d):
  # S stores the two ends of a geodesic segment
  # prev tells which of a,a^-1,b,b^-1 we last applied
  # d: depth countdown
  draw S # draw appropriate arc of circle
  if d < 1 : return
  if prev != 2 : recursion(a.S,   1,d-1)
  if prev != 1 : recursion(a^-1.S,2,d-1)
  if prev != 4 : recursion(b.S,   3,d-1)
  if prev != 3 : recursion(b^-1.S,4,d-1)
  
recursion(S0,0,depth)

Less loss: using a³=e and b⁷=e, still ignoring relations between a and b:

def recursion_a(S):
  draw S
  if d>0: for i from 1 to 2:
    recursion_b(a^i.S,d-1)

def recursion_b(S):
  draw S
  if d>0: for i from 1 to 6:
    recursion_a(b^i.S,d-1)
  
for i from 0 to 2:
  recursion_b(a^i.S0,depth)

How much loss?

The proportion of useful probes decreases exponentially with respect to the depth.

(means bad)

When to stop?

Next image courtesy of Ed Harriss.

Alternative to depth to stop recursion: when a segment gets small. Problem: some bigger segments may hide beyond.

By chance the ratio of the size of two segments at the same depth remains in a bounded range.

Yet many unnecessary segments need to be considered to be sure to include the visible ones.

The relations are generated by a³, b⁷, (ab)² and there is an algorithm (Dehn, Holt) to enumerate each element of the group only once.

This gets more complicated to code.

(Moreover ab.S = S, so only half of the group has to be considered.)

Raster methods

Bitmap images are arrays of pixels.
A raster method is simply:

for each line i:
  for each row j:
    compute the color of the pixel i,j

For the {3,7} group :

def compute_color(z0):
  z = z0
  while z is not in fundamental triangle:
    rotate z by b^i so that it falls in the blue cone
    rotate z by c if not in fundamental triangle
    # a max iteration counter can be added for security
  return a color depending on the final z

Cons	Pros
more computation (slower) gives bitmap instead of vector graphics aliasing near the boundary	easy to program easy to adapt max iterations (almost) not a problem

Number of transforms applied to z to get to the fundamental triangle.

Example 1: Coloring z according to sign im z' where z' is the representative of G.z in the fundamental triangle.

Example 2: Testing if HypDist(z',ℝ) > ε

Example 3: Some fancy coloring
depending on re(z') and im(z').

Example 4: Real-time rendering using the GPU. Works in the browser with WebGL.

Distance estimators

Using the derivative

J: Julia set of a rational map F.

A priori to draw a bitmap image of J we would like to be able to dectect whether J goes through a given pixel.

We will be a bit rough and instead try to estimate if the distance from the pixel center to J passes some threshold.

Worse: we will only estimate the distance up to some factor.

J: Julia set of a rational map F.

If you find any point a∈J then the set of its iterated preimages ⋃F^-n{a} is dense in J.

So J intersects B(z,r) ⟺ there is some n such that a∈FⁿB(z,r).

A daring simplification: do as if
FB(z, r) = B(F(z), r|F'(z)|).

This is good when r is small and z not too close to a critical point of F.

It works remarkably well for such a bold approximation.

A clear explanation of why is still missing. Related to bounded distorsion of inverse branches.

Distance estimators for Kleinian groups.

Good news: the image of a disk is a disk.

Next slide: for the {3,7} group, we start from B(z,ε), ε≈pixel-size. Iterate under a or b until z'=g.z falls in the fundamental domain, and we test whether g.B(z,ε) meets the boundary of a triangle.

Picture by Roice Nelson.

Real-time with WebGL:

Non-Fuchsian
Kleinian
groups

Even on a modern fast PC, it takes forever to draw a quasifuchsian group's limit set (like below) by drawing the images of a point under all group elements in a given word length ball.

The method for quasifuchsian groups in Indra's Pearls consists in drawing segments between a clever selection of words, properly ordered.

This yields fantastic images like the following by D. Wright:

What about raster methods?

How do you choose which element of the group to apply to a given pixel center or disk?

No advantage in exploring the whole group.

Need a guess of which group elements are more appropriate.

Not as easy as in the case of {3,7}.

Kleinian groups

The sphere S² is the boundary at infinity the hyperbolic space H³ and direct isometries of H³ extend to homographies of S². Kleinian groups act on the sphere S² and correspond to discrete groups G ⊂ isom₊(H³).

The space G\H³ is a hyperbolic 3-manifold (or an orbifold if G has finite order elements).

Reminder

Definition: the Dirichlet domain D associated to M∈H³ is the set of points in H³ that are closer to M than to any other point in the orbit G.M. It is open and convex (Voronoï cell).

Let us denote the set of points equidistant to A and B.

med(A,B).

For a Kleinian group G, D is polyhedral, bounded or unbounded, has finitely or infinitely many sides, supported by planes of the form med(M,g.M) with g∈G.

For a quasifuchsian group, D has finitely many faces and reaches the sphere at infinity along a big domain.

Let M∈H³ and D the associated Dirchlet domain.

For our proposed algorithm we need to find a finite subset K of G such that every face of D is contained in the median plane med(M,g.M) for some g∈K.

In my case I found such sets K by trial and error and with no certificate that they work… other than "the pictures look legitimate".

However, I think some talented programmer mathematicians have already created algorithms that automatically find such sets K.

Let M∈H³ and D the associated Dirchlet domain.

For every P∈H³, if P∉D then there exists g∈K such that dist(g.P,M) < dist(P,M).

We can thus find how to send P back to D with G:

loop:
  if for some g∈K, dist(g.P,M)<dist(P,M) :
    P = g.P
    continue loop
  else: exit loop

Proposed method: associate to each pixel one point P in the half-space model of H³ above the center of the disk B(z,r) and on the Euclidean sphere S(z,r).

To pair (P,z) ∈ H³×S² one associates a unique disk as follows: Through P passes a unique geodesic plane orthogonal to the geodesic line from P to z. This plane cuts S² into two disks, take the one containing z.

Caution: a given disk has many representatives.

Method:

Choose a center M∈H³, find K generating the associated Dirichlet domain D.
Identify one or a finite collection L of points on the limit set.
For each pixel: "iterate" (P,z) towards M until either
1. the associated disk contains a point in L,
2. or P enters D.
Color black or white according to (1) or (2).

Example: some QF group isomorphic to <a,b | (abAB)² = id>

K = {a, b, A, B, ab, ba, AB, BA, a⁷, A⁷, b⁷, B⁷}.

The Dirichlet domain D is a fundamental domain. Its impression at infinity gives us a fundamental domain U for the action of G on the ordinary set Ω = S² − Λ, where Λ is the limit set.

We can test whether the final disk, associated to (P_n,z_n), meets ∂U. This will detect the boundary of the tiles of the tesselation of Ω by G.U.