On Overlays and Minimization Diagrams

The overlay of 2≤m≤d minimization diagrams of n surfaces in ℝ ^d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in ℝ ^d+m−1. This elementary observation leads to a new bound on the complexity of the overlay of minimization diagrams of collections of d-variate semi-algebraic surfaces, a tight bound on the complexity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algorithmic implications are discussed. Work by V. Koltun was supported by NSF CAREER award CCF-0641402. Work by M. Sharir was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.