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.
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.