Boris Aronov, Marshall Wayne Bern, and David Eppstein

Cited by:

- Complexity of projected images of convex subdivisions
- The union of convex polyhedra in three dimensions
- The common exterior of convex polygons in the plane
- The robot localization problem
- Arrangements
- Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytopes
- Sparse arrangements and the number of views of polyhedral scenes
- A simple and efficient procedure for polyhedral assembly partitioning under infinitesimal motions
- Two-handed assembly sequencing
- Arrangements and their applications

This manuscript has not been published; it proves bounds on the complexity of arrangements of m polytopes, with a total of n faces, at most c of which have a common intersection. Some or all of the citations are for the close-to-trivial bound O(m^{ceil(d/2)} n^{floor(d/2)}). We then apply these bounds in the analysis of algorithms for finding combinatorially distinct minimum spanning trees formed by adding one Steiner point to a point set. See "On the number of minimal 1-Steiner trees" (same authors; DCG 1994) for closely related results on the number of possible such trees.