Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex part...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2007-10, Vol.23 (5), p.481-507
Main Authors: Aichholzer, O., Huemer, C., Kappes, S., Speckmann, B., Tóth, Cs. D.
Format: Article
Language:English
Subjects:
Computer science
Geometry
Graph theory
Mathematics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets. [PUBLICATION ABSTRACT]
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-007-0752-x