Arrangements of polytopes and the 1-Steiner problem

Boris Aronov, Marshall Wayne Bern, and David Eppstein

Cited by:

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.

Fano Experimental Web Server, D. Eppstein, School of Information & Computer Science, UC Irvine
Made on a Mac Valid XHTML 1.0!