"Lower and Upper Bounds for the Number of Polygons in the Minimum Convex Subdivision of Sets of Points in the Plane"

Carlos Nicolas
University of Kentucky

Monday, October 29, 2007
4:00 pm, 113 Patterson Office Tower

Abstract:

Given a finite set S of points in the plane, a convex subdivision (or convex partition) of S is a covering of the convex hull of S with non-overlapping empty convex polygons whose vertices are points of S. A minimum convex subdivision of S is one with a minimum number of polygons. Let G(S) be the number of polygons in a minimum convex subdivision of S. Define g_h(n) as the maximum value of G(S) among all the sets S of n points in general position in the plane with h extreme points. Let g(n) be the maximum value of g_h(n) for all h. I will show how to obtain lower and upper bounds for the functions g and g_h. Also, I will explain some cases in which these bounds are tight.