A study of convex covers in two or more dimensions
Thomas Caton Shermer, Patrice Belleville · 1995
The problem of covering polytopes using simple shapes is central to computational geometry. In particular, a lot of attention has been given to the problem of covering a simple polytope by convex pieces. We call a polytope Uk if there is a collection of k convex sets whose union is that polytope, and Bk if there is a collection of k convex subsets of the polytope whose union contains its boundary. This thesis studies several aspects of the recognition problem for Bk and Uk simple polytopes. We first give linear time algorithms to recognize B3 and U3 simple polygons. These algorithms are developed in three stages. In the first stage, we consider the convex subpolygons of a simple polygon P whose intersection with the boundary of P is a subset of a given set of m non-overlapping intervals. We show how to recognize the polygons whose boundary can be covered by k such subpolygons in 0(k3m2k-2 + TM(kmk-I)) time, where TM(n) is the time required to multiply two n x n matrices (currently known to be in ~ ( n ' . ~ ~ ~ ) ) . In the second stage, we characterize B3 polygons by proving that the boundary of every B3 polygon P can always be covered using a restricted class of convex subpolygons of P; this reduces the problem of recognizing B3 polygons to that solved in the first stage. Finally, we show how to prune almost all of the covers that this algorithm considers to recognize B3 and U3 polygons in linear time. We then study U2 polytopes in three-dimensional space (they are the same as B2 polytopes). We prove that they can be recognized in O(n1og n) time using O(n) space. We also show how to extend this algorithm to recognize U2 polytopes in ddimensional space in polynomial time, for every fixed value of d. Finally we present a negative result: we prove that the recognition problem for Bk or Uk polytopes in d-dimensional space is NP-hard for each fixed d 2 3 and k 2 3.