Faster Non-linear Parametric Search with Applications to Optimization and Dynamic Geometry

摘要

A technique for accelerating certain applications of parametric search to non-linear problems is presented, together with its applications to optimization on weighted graphs and to two problems in dynamic geomety on points moving in straight-line trajectories: computing the minimum diameter over all time and finding the time at which the length of the maximum spanning tree is minimized.