Planar Point Sets with Large Minimum Convex Partitions
Jesus Garc ́ õa-Lopez, Carlos M. Nicolás · 2006
Given a finite set S of points in the plane, a convex partition of S is a subdivision of the convex hull of S into nonoverlapping empty convex polygons with vertices in S. Let G(S) be the minimum m such that there exists a convex partition of S with at most m faces. Let F(n) be the maximum value of G(S) among all the sets of n points in the plane. It is known [1] that F(n) � n + 2 for n � 13. In this paper we show that, for n � 4 F(n) > 12 n 2