On overlays and minimization diagrams
Vladlen Koltun, Micha Sharir · 2006
The overlay of 2≤m≤d minimization diagrams of n surfaces in Rd is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in Rd+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 compleity of the overlay of minimization diagrams of collections of hyperplanes, and faster algorithms for constructing such overlays. Further algoithmic implications are discussed.