5 citations · 11 across the 16 of their papers we have counts for
24 papers
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
Haim Kaplan, Matthew J. Katz, Rachel Saban +1
We study the reverse shortest path problem on disk graphs in the plane. In this problem we consider the proximity graph of a set of disks in the plane of arbitrary radii: In th…
Minimum-link -Oriented Paths Visiting a Sequence of Regions in the Plane
Kerem Geva, Matthew J. Katz, Joseph S. B. Mitchell +1
Let be a set of -oriented disjoint segments in the plane, where is a given finite set of orientations that spans the plane, and let and be two…
Bottleneck Matching in the Plane
Matthew J. Katz, Micha Sharir
We present an algorithm for computing a bottleneck matching in a set of points in the plane, which runs in deterministic time, where is…
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
Pankaj K. Agarwal, Boris Aronov, Esther Ezra +2
Let be a set of flat (planar) semi-algebraic regions in of constant complexity (e.g., triangles, disks), which we call plates. We wish to preproces…
Efficient algorithms for optimization problems involving semi-algebraic range searching
Matthew J. Katz, Micha Sharir
We present a general technique, based on parametric search with some twist, for solving a variety of optimization problems on a set of semi-algebraic geometric objects of constant…
A 4-Approximation of the -MST
Stav Ashur, Matthew J. Katz
Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree spanning trees, w…