@inproceedings{dbcdfadb9e7a49f1befb4f30c85912f9,
title = "No Quadrangulation is extremely odd",
abstract = "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(nlogn) time, which is optimal, 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. Finally, our results imply that a fc-angulation of a set of points can be achieved with the addition of at most k — 3 extra points within the same time bound.",
author = "Prosenjit Bose and Godfried Toussaint",
note = "Publisher Copyright: {\textcopyright} 1995, Springer-Verlag.; 6th International Symposium on Algorithms and Computations, ISAAC 1995 ; Conference date: 04-12-1995 Through 06-12-1995",
year = "1995",
doi = "10.1007/bfb0015443",
language = "English (US)",
isbn = "3540605738",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "372--381",
editor = "John Staples and Peter Eades and Naoki Katoh and Alistair Moffat",
booktitle = "Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings",
}