Planar point sets with large minimum convex decompositions

García López De Lacalle, Jesús y 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.

Descripción

Título: Planar point sets with large minimum convex decompositions
Autor/es:
  • García López De Lacalle, Jesús
  • Nicolás, Carlos M.
Tipo de Documento: Artículo
Título de Revista/Publicación: Graphs and Combinatorics
Fecha: 2013
Volumen: 29
Materias:
Palabras Clave Informales: Convex decompositions,Triangulations, Empty polygons.
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (885kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 33183
Identificador DC: http://oa.upm.es/33183/
Identificador OAI: oai:oa.upm.es:33183
Identificador DOI: 10.1007/s00373-012-1181-z
URL Oficial: http://link.springer.com/journal/373
Depositado por: Memoria Investigacion
Depositado el: 20 Feb 2015 12:45
Ultima Modificación: 20 Feb 2015 12:45
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM