Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (885kB) | Preview |
Planar point sets with large minimum convex decompositions
Citation
García López De Lacalle, Jesús and Nicolás, Carlos M. (2013). Planar point sets with large minimum convex decompositions. "Graphs and Combinatorics", v. 29 (n. 5); pp. 1347-1353. ISSN 0911-0119. https://doi.org/10.1007/s00373-012-1181-z.
Description
| Title: | Planar point sets with large minimum convex decompositions |
|---|---|
| Author/s: |
|
| Item Type: | Article |
| Título de Revista/Publicación: | Graphs and Combinatorics |
| Date: | 2013 |
| ISSN: | 0911-0119 |
| Volume: | 29 |
| Subjects: | |
| Freetext Keywords: | Convex decompositions,Triangulations, Empty polygons. |
| Faculty: | E.U. de Informática (UPM) |
| Department: | Matemática Aplicada |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
We show the existence of sets with n points (n ? 4) for which every convex decomposition contains more than (35/32)n?(3/2) polygons,which refutes the conjecture that for every set of n points there is a convex decomposition with at most n+C polygons. For sets having exactly three extreme pointswe show that more than n+sqr(2(n ? 3))?4 polygons may be necessary to form a convex decomposition.
More information
| Item ID: | 33183 |
|---|---|
| DC Identifier: | https://oa.upm.es/33183/ |
| OAI Identifier: | oai:oa.upm.es:33183 |
| DOI: | 10.1007/s00373-012-1181-z |
| Official URL: | http://link.springer.com/journal/373 |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 20 Feb 2015 12:45 |
| Last Modified: | 20 Feb 2015 12:45 |
