Planar point sets with large minimum convex decompositions

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:
  • García López De Lacalle, Jesús
  • Nicolás, Carlos M.
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (885kB) | Preview

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM