s.geom

NAME

s.geom - Computes Delaunay triangulation, MinMax-Angle triangulation, MinMax-Slope triangulation, MaxMin-Height triangulation, Regular triangulation, planesweep triangulation, Voronoi diagram, and convex hull of sites in 2 and 2 1/2 dimensions.

SYNOPSIS

s.geom
s.geom help
s.geom input=name output=name [precision=value] [operation=name]

DESCRIPTION

s.geom takes a sites file as input and computes various triangulations, the Voronoi diagram, or the convex hull of the sites. The z-coordinate is read from the description field if it is specified, otherwise 0 is assumed. The z-coordinate is used for the MinMax-slope triangulation and for the regular triangulation (where it is interpreted as the weight of the site). For all other computations the z-coordinate is ignored.

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 MaxMin-height and MinMax-slope triangulations are similar. The algorithms used for the computations are not heuristics, they actually achieve the optimum.

The regular triangulation is the weighted version of the delaunay triangulation (weights are assigned to the sites, the delaunay triangulation corresponds to the regular triangulation where all the sites have identical weights).

The output is saved in vector file format.

OPTIONS

Parameters:

input=name: Input vector (level 2) file.
output=name: Output vector file.
precision=value: Number of significant positions after the decimal point. (default is 0).
operation=name: One of the following: sweep, delaunay, angle, height, slope, hull. These correspond to the planesweep triangulation, Delaunay triangulation, MinMax-angle triangulation, MaxMin-height triangulation, MinMax-slope triangulation, regular triangulation, Voronoi diagram, and convex hull, respectively. (default is Delaunay triangulation).

NOTE

Only the sites which fall into the current region are used for the computations.

The computation times for the various operations depends strongly on the algorithm used.

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 apprx. 16 decimal digits).

BUGS

Some fields of the header in the output file are not properly set.

REFERENCES

[BeEd] M.Bern, H. Edelsbrunner, D. Eppstein, S. Mitchel, T.S. Tan. Edge Insertion for Optimal Triangulations. In Proc. 1st Latin American Sympos. Theoret. Informatics 1992, 46--60.

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

AUTHOR

Roman Waupotitsch