On Convex Quadrangulations of Point Sets on the Plane

摘要: Let Pn be a set of n points on the plane in general position, ≥ 4. A convex quadrangulation is partitioning hull Conv(Pn) into quadrilaterals such that their vertices are elements Pn, and no element lies interior any quadrilateral. It straightforward to see if P admits quadrilaterization, its must have an even number vertices. In [6] it was proved has points, then by adding at most •n/• Steiner hull, we can always obtain point quadrangulation. The authors also show n/• sometimes necessary. this paper how improve upper lower bounds +2 respectively. fact, prove bound n, with long unenlightening case analysis (over fifty cases!) + 2, for details [9].