Advances in Geometric Algorithms and Robust Optimization

The field of geometric algorithms is moving towards developing more efficient and robust methods for solving complex problems. Researchers are focusing on improving the running time of algorithms for calculating distances and finding optimal solutions in various geometric settings. One area of interest is the computation of Fréchet distances between curves and trajectories, with a focus on achieving near-linear time complexity. Another direction is the development of algorithms for solving robust optimization problems, including those with uncertain or dynamic parameters. Notably, new variants of geometric hitting set problems have been proposed, which can be solved in strongly polynomial time under certain conditions. Additionally, there is a growing interest in applying these algorithms to real-world problems, such as trajectory clustering and coverage maximization. Noteworthy papers include: The paper on the $L_1$-geodesic Fréchet distance between two curves on the boundary of a simple polygon, which presents a near-linear time exact algorithm. The work on hitting and covering affine families of convex polyhedra, which proposes new variants of geometric hitting set problems and shows they can be solved in strongly polynomial time.

Sources

A near-linear time exact algorithm for the $L_1$-geodesic Fr\'echet distance between two curves on the boundary of a simple polygon

A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D

Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization

Fr\'echet Distance in Unweighted Planar Graphs

Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better

Built with on top of