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:
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: