Given a set 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 
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 points, which is optimal. We also provide an
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 (presented in section 4)
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.