Characterizing and efficiently computing quadrangulations of planar point sets

Given a set S of n points in the plane, a quadrangulation of S is a planar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except possibly the outer face) is a quadrilateral. We show that S admits a quadrangulation if and only if S does not have an odd number of extreme points. If S admits a quadrangulation, we present an algorithm that computes a quadrangulation of S in O(n log n) time even in the presence of collinear points. If S does not admit a quadrangulation, then our algorithm can quadrangulate S with the addition of one extra point, which is optimal. We also provide an Ω(n log n) time lower bound for the problem. Our results imply that a k-angulation of a set of points can be achieved with the addition of at most k - 3 extra points within the same time bound. Finally, we present an experimental comparison between three quadrangulation algorithms which shows that the Spiraling Rotating Calipers (SRC) algorithm produces quadrangulations with the greatest number of convex quadrilaterals as well as those with the smallest difference between the average minimum and maximum angle over all quadrangles.