Efficient algorithms for optimization problems involving semi-algebraic range searching

Matthew J. Katz, Micha Sharir

We present a general technique, based on parametric search with some twist, for solving a variety of optimization problems on a set of semi-algebraic geometric objects of constant…