Quadrangulations of planar sets

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

Abstract

Given a set S such as a polygon or a set of points, a quadrangulation of S is a partition of the interior of S, if 5 is a polygon, or the interior of the convex hull of S, if 5 is a set of points, into quadrangles (quadrilaterals) obtained by inserting edges between pairs of points (diagonals between vertices of the polygon) such that the edges intersect each other only at their end points. Not all polygons or sets of points admit quadrangulations, even when the quadrangles are not required to be convex (convex quadrangulations). In this paper we briefly survey some recent results concerning the characterization of those planar sets that always admit quadrangulations (convex and non-convex) as well as some related computational problems.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
EditorsSelim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
PublisherSpringer Verlag
Pages218-227
Number of pages10
ISBN (Print)3540602208, 9783540602200
DOIs
StatePublished - 1995
Event4th Workshop on Algorithms and Data Structures, WADS 1995 - Kingston, Canada
Duration: Aug 16 1995Aug 18 1995

Publication series

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

Other

Other4th Workshop on Algorithms and Data Structures, WADS 1995
CountryCanada
CityKingston
Period8/16/958/18/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Quadrangulations of planar sets'. Together they form a unique fingerprint.

Cite this