Forgot your password?
Recent Advances in Geometric Optimization
Wednesday, November 2nd, 4:10pm Tel Aviv time (3:10pm CET)
Micha Sharir, Tel Aviv University
Abstract:
We resurrect, extend and generalize a technique, developed 7 years ago for a Frechet distance problem,
and show that it can solve a large collection of geometric optimization problems, significantly improving known solutions,
for example for the reverse shortest path problem on unit-disk graphs, and obtaining new and fast solutions to other problems.
The technique is a simpler alternative to (or variant of) parametric search, for problems where the decision procedure is hard to
parallelize. The new algorithms make effective use of, and develop further, semi-algebraic range searching, a central topic in
geometry, where efficient implementations of the technique have emerged only very recently.
Joint work with Pankaj Agarwal and Matya Katz
