next up previous
Next: User's Guide Up: The algorithms Previous: Groups


To find the fundamental polygon we use the following theorem

Figure: Fundamental polygon of theorem gif

Theorem 1.

 Let be integers greater or equal than two and let be an integer greater than two, excepting the case when is three and all are equal to two. Then for each in an open set in (if is greater than three; if is three), there exists a hyperbolic polygon (see figure gif) with consecutive sides of lengths and respective interior angles , where (if is greater than three), , and are uniquely determined and satisfy

Moreover, for any such polygon, the group generated by the elliptic elements which pair consecutive sides of lengths , is a Fuchsian group with the given fundamental polygon; furthermore, uniformizes with signature and has a presentation of the form


Proof: See [GR93].

Still following [GR93] we define define a homomorphism

by extension of , for ; then is a torsion-free Fuchsian group; in fact, it is the smallest normal subgroup of generated by the words . Also, is a compact Riemann surfaces of genus , and the natural projection from to is a Galois covering with the prescribed signature and covering group which is isomorphic to .

Figure: Polygon drawn using DFS labeling

Figure: Polygon drawn using BFS labeling

Figure: Polygon drawn using ``symmetric'' BFS labeling

So we want to construct the fundamental region for , taking images of under elements of . To choose this images we label each element in with a word on the generators and then use that word to construct an element in , standard techniques, such as breadth first search (BFS) or depth first search (DFS), produce strange labelings that leaded to unconnected or non-symmetrical polygons, see for example figures gif, gif and gif; in all of them is

The best results are obtained using a modified version of BFS, the idea is to maintain symmetry according to the first generator, gif let us call

the first generator; as in BFS a queue is used to keep the vertices that need processing, this queue is initialized with the identity vertex and those vertices where the user has already chosen a label (this is done to respect user preference, see below) then for each vertex

in the queue the vertices corresponding to

are labeled as

, where

is the label for

. Now each vertex

in the queue is processed as follows, unless already labeled a neighbour


across an edge coloured

is labeled

, where

is the label of

, and added to the queue (this is normal BFS), the vertices

are labeled

and added to the queue, unless they have been labeled already; the process continues until the queue is empty.

Sometimes the user may want a different labeling of the group, Unifpack provides methods to change some words and all labeling algorithms respect user preferences.

Figure: A fundamental polygon parametrized by side lengths

Figure: A fundamental polygon parametrized by angles

Sometimes a better set of parameters than the ones provided by theorem gif can be found (see figures gif and gif), to exploit this possibility Unifpack defines polygon types, when calculating the polygon from the group it tries to determine the best polygon type for the group, mechanisms are provided to add new (user defined) polygon types.

A polygon type also calculates initial or default values for the parameters it take, the fundamental region

the generators of the group

, checks if it can handle a presentation, provides methods to draw

and I/O functions.

next up previous
Next: User's Guide Up: The algorithms Previous: Groups