Planar point sets with large minimum convex decompositions


Autoria(s): García López De Lacalle, Jesús; Nicolás, Carlos M.
Data(s)

2013

Resumo

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.

Formato

application/pdf

Identificador

http://oa.upm.es/33183/

Idioma(s)

eng

Publicador

E.U. de Informática (UPM)

Relação

http://oa.upm.es/33183/1/INVE_MEM_2013_181556.pdf

http://link.springer.com/journal/373

info:eu-repo/semantics/altIdentifier/doi/10.1007/s00373-012-1181-z

Direitos

http://creativecommons.org/licenses/by-nc-nd/3.0/es/

info:eu-repo/semantics/openAccess

Fonte

Graphs and Combinatorics, ISSN 0911-0119, 2013, Vol. 29, No. 5

Palavras-Chave #Matemáticas #Informática
Tipo

info:eu-repo/semantics/article

Artículo

PeerReviewed