Planar point sets with large minimum convex decompositions
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 | |
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 |