The MinMax-angle triangulation is the triangulation for the sites which minmizes (lexicographically) the sorted vector of all the angles of triangles in the triangulation. The constrained version also minimizes this vector but under the constrained that prescribed (i.e. input) edges are part of the final triangulation. The MaxMin-height and MinMax-slope triangulations are similar. The algorithms used for the computations are not heuristics, they actually achieve the optimum.
We use a simple extension of the algorithm used to compute the Delaunay triangulation in s.geom to compute a triangulation which can be considered an approximatoin of the constrained Delaunay triangulation. However, this is only a (bad?) heuristic.
The output is saved in vector file format. Edge labels of input edges will also be attached to the corresponding output edges.
The plansweep triangulation and convex hull computation require O(n log n) operations in the worst case [Ed]. The Delaunay heuristic needs O(n^2) time in the worst case, however it performs much faster in practice. The MinMax-angle and MaxMin-height triangulations need O(n^2 log n) operations [BeEd, EdTa], and the MinMax-slope triangulation needs O(n^3) operations [BeEd].
Internally, the coordinates of the sites are stored in fix-point format. Therefore, the number of decimal digits cannot exceed 64 bit (or approx. 16 decimal digits).
It is important that the input vector file is reasonably "clean". The current implementation of v.geom takes care of loops (i.e. zero length edges), duplicate edges, and edges which are collinear and overlapping. However, because of the internal representation of coordinates in fix-point format it can happen that certain anomalies are introduced. For examples edges can cross although they don't in the input data. Currently, the program does not test for such cases. If it occures one of two situations will happen. Either, the planesweep algorithm terminates with a segmentation fault, or it will loop forever. For the data where we had problems these problems could be eliminated if we first used v.spag.
[Ed] H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, Germany, 1987.
[EdSh] H. Edelsbrunner, N. R. Shah. Incremental Flipping Works for Regular Triangulations. In Proc. 8th Ann. Sympos. Comput. Geom. 1992, 43-52.
[EdTa] H. Edelsbrunner, T.S. Tan and R. Waupotitsch. An O(n^2 log n) Time Algorithm for the MinMax Angle Triangulation. SIAM J. Sci. Statist. Comput. 13 1992, 994-1008.
Last changed: $Date$