Quadrangulations
Although triangulations are a much more commonly used structure, recently quadrangulations have been shown to be prefferable in some particular cases, such as scattered data interpolation and finite element methods.
A quadrangulation is essentially a subdivision of a set of points into quadrilaterals. Some essential differences (aside the obvious ones) with triangulations should be noted:
First, not all sets of points admit quadrangulations. In fact, only even-numbered sets do. For odd-numbered sets, additional points (called Steiner points) are sometimes added to the original set, in order to be able to obtain a quadrangulation.
In addition, it is often desired that the quadrilaterals obtained have some "nice" properties, like convexity. This issue is irrelevant in triangulations.
Many simple quadrangulation algorithms exist. For instance, consider triangulating a set of points first, and then adding a Steiner point in the interior of each triangle, and at the midpoint of each edge. Connecting these new points yields a quadrangulation (this idea is due to DeBerg).
Bose and Toussaint (1997) propose starting with the spiral triangulation of a set of points and removing diagonals, in order to obtain a quadrangulation.
If the set of points is even-numbered, then every second diagonal (added during the spiral triangulation algorithm) is removed, yielding a quadrangulation. If there is an odd number of points, then starting from the last diagonal added, every other diagonal (i.e. the last, the third to last, etc.) is removed, a Steiner point is added near the first diagonal, which is removed. The following ilustrates the first case (even-numbered set of points). The spiral triangulation (left), and the resulting quadrangulation (right).
Since the diagonal removal procedure (and necessary updates) takes O(n) time, this quadrangulation algorithm has the same time complexity as the spiral triangulation one. Among the advantages of this algorithm are its simplcity in concept and implementation (once the convex spiral has been obtained), and the fact that it yields a "nicer" quadrangulation than many rival algorithms.
The next set of problems focuses on convex polygons, and specifically, operations on convex hulls, such as merging two convex hulls.
December 17th, 1998