3 papers
cs.CG2026
Efficient Algorithms for the Bottleneck Path Problem in Geometric Graphs
Matthew J. Katz, Rachel Saban, Micha Sharir
We present efficient algorithms for the bottleneck path problem in two geometric settings that arise naturally in applications: directional-antenna graphs in the plane with antenna…
cs.CG2026
Dynamic Nearest-Neighbor Searching Under General Metrics in and Its Applications
Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir
Let be a compact, centrally-symmetric, strictly-convex region in , which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding me…
cs.CG2024
Robustly Guarding Polygons
Rathish Das, Omrit Filtser, Matthew J. Katz +1
We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point gua…