Personal tools
You are here: Home CG seminar 2023 Recent Advances in Geometric Optimization
« January 2023 »
January
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Recent Advances in Geometric Optimization

Wednesday, November 2nd, 4:10pm Tel Aviv time (3:10pm CET)

underline

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
Document Actions