No Quadrangulation is extremely odd

Prosenjit Bose, Godfried Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings
EditorsJohn Staples, Peter Eades, Naoki Katoh, Alistair Moffat
PublisherSpringer Verlag
Pages372-381
Number of pages10
ISBN (Print)3540605738, 9783540605737
DOIs
StatePublished - 1995
Event6th International Symposium on Algorithms and Computations, ISAAC 1995 - Cairns, Australia
Duration: Dec 4 1995Dec 6 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1004
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Symposium on Algorithms and Computations, ISAAC 1995
CountryAustralia
CityCairns
Period12/4/9512/6/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'No Quadrangulation is extremely odd'. Together they form a unique fingerprint.

  • Cite this

    Bose, P., & Toussaint, G. (1995). No Quadrangulation is extremely odd. In J. Staples, P. Eades, N. Katoh, & A. Moffat (Eds.), Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings (pp. 372-381). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1004). Springer Verlag. https://doi.org/10.1007/bfb0015443