# Simple triangulation over flat torus

This is somewhat of a computational question: let me know if it is inappropriate.

I have a flat torus with sone random points marked.

I would like to compute a triangulation of said torus such that my points are the vertexes of the triangulation.

A bit of googling has not given me any results. My naive idea would be to start from the fully connected graph, and every time two edges cross, simply remove one of them. Unfortunately this looks like it's going to be quite expensive, as I have $$n^2$$ edges each of which can potentially intersect all of the others. I also looked into the Delauney triangulation, but I am not sure it would work on an generic torus, and moreover I have no idea on how to implement it successfully. It also seems rather overkill, since I do not need my triangulation to have any special property.

Is there a simple, greedy way to get a triangulation in non-prohibitive time?

Thank you.

• Is it really significant that we are on a torus? What would you do with the same problem on a plane? Dec 17 '18 at 12:11
• Well, a torus is compact while a plane is not. I would like to eventually generalize this to a generic surface, so I picked a torus to avoid plane-specific solutions. Dec 17 '18 at 12:46
• Do you want a good triangulation? It seems relatively easy to generate a triangulation in which many of the triangles could be very narrow. Dec 17 '18 at 13:30
• Well, more of a "good enough" triangulation. This is mostly for testing a few ideas of mine, so ease of implementation is the first concern. Dec 17 '18 at 14:39
• I see a possible impediment. If an edge is specified only by its two endpoints, with some kind of rules based on the relative positions of points to decide which way do draw the edge, it is possible that you put $n$ points on the torus in such a way that the complete graph on those $n$ points consists of a polygon of at least $4$ sides, plus additional edges inside the polygon. I think there is then no way to triangulate the portion of the torus outside the polygon. Dec 17 '18 at 19:52

It is possible to construct a triangulation of $$n$$ points on the flat torus in $$O(n)$$ time by "brute force" as follows, at least if the points are in general position. I'll assume we're working on the square flat torus, obtained by identifying opposite sides of an axis-aligned unit square.

First sort the points by their $$x$$-coordinates and connect them into a polygonal cycle $$P$$. Then we can triangulate above $$P$$ by repeatedly cutting off a triangle $$pqr$$ whenever $$p$$ lies below the geodesic segment $$pr$$. Similarly, we can triangulate below $$P$$ by repeatedly cutting off a triangle $$pqr$$ whenever $$p$$ lies above the geodesic segment $$pr$$. This triangle cutting can be implemented in linear time using a stack, similar to the Graham scan convex hull algorithm.

After both these phases, we have triangulated the points on the square flat cylinder obtained by identifying the left and right sides of the unit square. The top and bottom edges of this triangulation are closed horizontal geodesics, passing through the "highest" point $$a$$ and the lowest point $$z$$. To complete the toroidal triangulation, we can extend two diagonals upward from $$a$$ to $$z$$.

In the following figure, the heavy black segments show the initial polygonal cycle $$P$$, the edges of the upper triangulation of $$P$$ are red, the edges of the lower triangulation of $$P$$ are green, and the final two diagonals between the highest and lowest points of $$P$$ are blue. The flat torus can be constucted by identifying the opposite sides of a square in the plane.

Take an element in center of such a square and an element at the middle of each side. Draw a segment between the element in the center and the corners of the square, and between the element in the center and the elements in the middle of each side. This induces a triangulation of the torus.

You can generalize this for the $$n$$-torus which can be constructed by identifying opposite face of a parallepiped, triangulate each face such that no point is identifyied in the quotient and draw a segment between a point in the center and the vertices of the triangulation on the faces.

• I need my triangulation to have vertexes on specific assigned points. Dec 17 '18 at 12:47