Algorithms for balanced partitioning of polygons and point sets
Matthew Díaz · 1991
This thesis presents algorithms for partitioning point sets and polygons. We first consider various types of min/max or adversarial partitionings--for a particular type of partitioning device, one person selects an object or objects which restrict the partition and a second person makes a partition given that restriction. The goal of the second person is to minimize (maximize) a metric associated with the partition while the goal of the first person is to choose the partitioning restriction so as to force the second person to maximize (minimize) the metric. We present algorithms for determining the following types of min/max problems: (1) The best pair of points to choose from a set such that any circle which includes those points must necessarily include many points of the set. (2) The point in a polygon such that the minimum area of the polygon enclosed by any halfplane which includes that point is maximized. (3) The point(s) in a polygon such that the minimum (maximum) length chord through that point is maximized (minimized). (4) The point in a polygon such that the minimum ratio of the lengths of the chord to either side of the point is maximized. We then discuss partitions of point sets and polygons into equal sized regions, describing algorithms to accomplish the following: (1) Bisect and foursect the area of a simple polygon. (2) Find a pair of mutually orthogonal lines which foursection a point set or convex polygon. (3) Find three mutually orthogonal planes which eightsection a point set in three dimensions. We conclude with open problems and directions for future research.