Empty-shape triangulation algorithms
Dereck Meek, Timothy D. Lambert · 1994
The Delaunay triangulation of a set of sites (points in the plane) can be defined as the triangulation with the property that the circumcircle of each triangle is empty (contains no site). I generalize this to define empty-shape triangulations. An empty-shape triangulation is defined by a set of shapes with the property that any triangle has a unique circumscribing shape. The Delaunay triagulation is the empty-shape triagulation where the shapes consist of the set of all circles. In this thesis I develop a taxonomy for triangulation algorithms, describe and implement a plane sweep algorithm for empty-shape triangulations, describe algorithms for constrained empty-shape triangulations and an algorithm for higher-dimensional empty-shape triangulations. I implement an algorithm for computing convex-distance-function Delaunay triangulations by extending them to empty-shape triangulations and then extracting the appropriate subtriangulation. Two properties of the Delaunay triangulation are necessary for the correctness of the known efficient algorithms. I prove that the only triangulations with these properties are empty-shape triangulations. I analyze, implement and measure the performance of Delaunay triangulation algorithms on random convex polygons. There is no generally accepted definition of what a random convex polygon is. I give several operational definitions, designs efficient algorithms and implement some of them.