Raster methods
Imaging Holomorphic dynamics
& Kleinian groups
Ad: https://www.math.ubordeaux.fr/wikiklein/
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,d1)
if prev != 1 : recursion(a^1.S,2,d1)
if prev != 4 : recursion(b.S, 3,d1)
if prev != 3 : recursion(b^1.S,4,d1)
recursion(S0,0,depth)
Less loss: using a^{3}=e and b^{7}=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,d1)
def recursion_b(S):
draw S
if d>0: for i from 1 to 6:
recursion_a(b^i.S,d1)
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^{3}, b^{7}, (ab)^{2} 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:
Realtime 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^{n}B(z,r).
A daring simplification: do as if
FB(z, r) = B(F(z), rF'(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,ε), ε≈pixelsize. 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.
NonFuchsian
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^{2} is the boundary at infinity the hyperbolic space H^{3} and direct isometries of H^{3} extend to homographies of S^{2}.
Kleinian groups act on the sphere S^{2} and correspond to discrete groups G ⊂ isom_{+}(H^{3}).
The space G\H^{3} is a hyperbolic 3manifold (or an orbifold if G has finite order elements).
Reminder
Definition: the Dirichlet domain D associated to M∈H^{3} is the set of points in H^{3} 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^{3} 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^{3} and D the associated Dirchlet domain.
For every P∈H^{3}, 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 halfspace model of H^{3} above the center of the disk B(z,r) and on the Euclidean sphere S(z,r).
To pair (P,z) ∈ H^{3}×S^{2} 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^{2} into two disks, take the one containing z.
Caution: a given disk has many representatives.
Method:
 Choose a center M∈H^{3}, 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
 the associated disk contains a point in L,
 or P enters D.
 Color black or white according to (1) or (2).
Example: some QF group isomorphic to <a,b  (abAB)^{2} = id>
K = {a, b, A, B, ab, ba, AB, BA, a^{7}, A^{7}, b^{7}, B^{7}}.
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^{2} − Λ, 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.
K = { A,B,a,b,AB,ba,BA,ab }
K = { A,B,a,b,AB,ba,BA,ab }
A fast algorithm for limit sets of Kleinian groups with the Maskit
parametrisation, [Jos Leys], January 2017