Polytopes in arrangements

Consider an arrangement of n hyperplanes in R-d. Families of convex polytop es whose boundaries are contained in the union of the hyperplanes are the s ubject of this paper. We aim to bound their maximum combinatorial complexit y. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openl y disjoint have also been considered in the past. However, no nontrivial bo und was known for the general case where the polytopes may have overlapping interiors, for d > 2. We analyze families of polytopes that do not share v ertices. In R-3 we show an O (k(1/3)n(2)) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensi onal versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in R-d is Omega ( k(1/2)n(d/2)) which is a factor of rootn away from the best known upper bou nd in the range n(d-2) less than or equal to k less than or equal to n(d). The case where 1 less than or equal to k less than or equal to n(d-2) is co mpletely resolved as a known Theta (kn) bound for cells applies here.