Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets 


The problem of triangulations of point sets have received considerable attention. However, for certain applications, quadrangulations of point sets may be more desirable. Particularly for:

Methods have been proposed to convert a triangle mesh into a quadrangular mesh in using up to O(n) extra points (these are called Steiner points).

The above applications provide motivation for more study of quadrangulations. It has been shown that arbitrary simple orthogonal polygons can always be decomposed into convex quadrangles, and that there is a lower bound of time on the complexity of this problem. However, an arbitrary simple polygon does not necessarily admit a quadrangulation, even if convexity of the resulting quadrangles is not a requirement. On the other hand, if we are allowed to add Steiner points, then we can always obtain convex quadrangulations of those.

The paper presented here characterizes sets of points that admit a quadrangulation, and presents an algorithm that computes a quadrangulation of S in time, even in the presence of collinear points. If S does not admit a quadrangulation, then the algorithm can quadrangulate S with the addition of one extra point, which is optimal.

There is also an experimental comparison with two other quadrangulation algorithms that shows that the Spiraling Rotating Calipers (the algorithm introduced here) produces quadrangulations with:

Main Page | Abstract | Introduction | Algorithm | Results | Applet | References | Comments