Planar Point Sets With Large Minimum Convex Decompositions |
| |
| Authors: | Jesús García-López Carlos M. Nicolás |
| |
| Affiliation: | 1. Departamento de Matemática Aplicada, Escuela Universitaria de Informática, Polytechnical University of Madrid, 28031, Madrid, Spain
2. Department of Mathematics and Statistics, University of North Carolina Greensboro, Greensboro, NC, 27402, USA
|
| |
| Abstract: | We show the existence of sets with $n$ points ( $nge 4$ ) for which every convex decomposition contains more than $frac{35}{32}n-frac{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 points we show that more than $n+sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
