Triangulation Flip Graph

Small CLI binary that computes all the convex triangulations on a 2D plane connected.

Usage

Provide an single string as the argument for the set of points being triangulated.

Take for example a set of points given by (-1,-1) (-1,0) (-1,1) (0,-1) (0,0) (0,1) (1,-1).

./triangulation-graph "(-1,-1) (-1,0) (-1,1) (0,-1) (0,0) (0,1) (1,-1)"

Note: The number of triangulations of a set of $n$ points in the plane growns exponentially with $n$.

The average counts and time are obtained by taking a sample of uniformly distributed points.

Output

The program outputs all the possible triangulations as a list of 3-tuples of points. Each triangulation is printed in a new line. The last line in the output is the edges of the graph connecting the triangulation by a flip operation (labelled by 0, 1, ..., in the same order).

((-1 -1,-1 0,0 -1), (-1 0,-1 1,0 0), (-1 0,0 -1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 -1), (0 0,1 -1,1 0))
((-1 -1,-1 0,0 0), (-1 -1,0 -1,0 0), (-1 0,-1 1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 -1), (0 0,1 -1,1 0))
((-1 -1,-1 0,0 -1), (-1 0,-1 1,0 0), (-1 0,0 -1,1 -1), (-1 0,0 0,1 -1), (-1 1,0 0,1 0), (0 0,1 -1,1 0))
((-1 -1,-1 0,0 -1), (-1 0,-1 1,0 0), (-1 0,0 -1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 0), (0 -1,1 -1,1 0))
((-1 -1,-1 0,0 -1), (-1 0,-1 1,0 -1), (-1 1,0 -1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 -1), (0 0,1 -1,1 0))
((-1 -1,-1 0,0 0), (-1 -1,0 -1,0 0), (-1 0,-1 1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 0), (0 -1,1 -1,1 0))
((-1 -1,-1 0,0 -1), (-1 0,-1 1,0 -1), (-1 1,0 -1,0 0), (-1 1,0 0,1 0), (0 -1,0 0,1 0), (0 -1,1 -1,1 0))
((-1 -1,-1 0,0 0), (-1 -1,0 -1,1 0), (-1 -1,0 0,1 0), (-1 0,-1 1,0 0), (-1 1,0 0,1 0), (0 -1,1 -1,1 0))
{7,5} {6,4} {6,3} {5,3} {5,1} {4,6} {3,0} {5,7} {3,6} {3,5} {2,0} {1,5} {1,0} {0,4} {0,2} {0,3} {4,0} {0,1}

Graphically, the result is the following triangulations,

including the graph of flip operations.