Discrete CATS Seminar
####
**
UNIVERSITY OF KENTUCKY **

DISCRETE CATS SEMINAR

DISCRETE MATH AND COMBINATORICS: ALGEBRAIC & TOPOLOGICAL SEMINAR

113 PATTERSON OFFICE TOWER

FALL 2007

##
"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.