|
|||||
|
|
Decompositions,Partitions, and Coverings with Convex Polygons and Pseudo-Triangles |
|
| Authors: | O. Aichholzer C. Huemer S. Kappes B. Speckmann Cs. D. Tóth |
| Affiliation: | (1) Institute for Software Technology, Graz University of Technology, Austria;(2) Departament de Matemática Aplicada II, Univ. Poli. de Catalunya, Spain;(3) Department of Mathematics, , TU Berlin, Germany;(4) Department of Mathematics and Computer Science, , TU Eindhoven, Netherland;(5) Department of Mathematics, MIT, Cambridege, MA 02144, USA |
| Abstract: | 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. |
| Keywords: | Partitions decompositions planar point sets Ramsey-type results |
| 本文献已被 SpringerLink 等数据库收录！ | |