Some Geometric Partitioning Questions, Answers, Algorithms

May 5, 2015

It is known that for a given convex body $K$ in $\mathbb{R}^3$, there are three planes whose octants each cut off the same volume in $K$. In fact "volume" can be replaced by a "nice" measure $m$. In addition for dimension $d>4$, the analogous statement is in general, false. The situation when $d=4$ is tantalizingly open.

This example highlights some main concerns of geometric partitioning, namely what kinds of partitions of geometric objects always exist and what kinds need not exist. Another aspect of this topic is an algorithmic one that arises when the measure m is counting measure w.r.t. a given set of n points. Here a concern is to learn the complexity of the partitioning task, as well as to create good algorithms for it. I will discuss these ideas through a set of examples in which there are some known results, and also some new ones.