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 pl anar subdivision whose vertices are the points of S, whose outer face is the convex hull of S, and every face of the subdivision (except pos sibly the outer face) is a quadrilateral. We show that S admits a quad rangulation if and only if S does not have an odd number of extreme po ints. If S admits a quadrangulation, we present an algorithm that comp utes 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 alg orithm can quadrangulate S with the addition of one extra point, which is optimal. We also provide an Omega(n log n) time lower bound for th e problem. Our results imply that a k-angulation of a set of points ca n be achieved with the addition of at most k - 3 extra points within t he same time bound. Finally, we present an experimental comparison bet ween three quadrangulation algorithms which shows that the Spiraling R otating Calipers (SRC) algorithm produces quadrangulations with the gr eatest number of convex quadrilaterals as well as those with the small est difference between the average minimum and maximum angle over all quadrangles. (C) 1997 Elsevier Science B.V.