Zobrazeno 1 - 10
of 327
pro vyhledávání: '"Katz, Matthew J."'
It is unlikely that the discrete Fr\'echet distance between two curves of length $n$ can be computed in strictly subquadratic time. We thus consider the setting where one of the curves, $P$, is known in advance. In particular, we wish to construct da
Externí odkaz:
http://arxiv.org/abs/2404.04065
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 guards in a polygon is a notoriously challenging area of investigation, w
Externí odkaz:
http://arxiv.org/abs/2403.11861
Autor:
Farhana, Tsuri, Katz, Matthew J.
We initiate the study of spanners under the Hausdorff and Fr\'echet distances. We show that any $t$-spanner of a planar point-set $S$ is a $\frac{\sqrt{t^2-1}}{2}$-Hausdorff-spanner and a $\min\{\frac{t}{2},\frac{\sqrt{t^2-t}}{\sqrt{2}}\}$-Fr\'echet
Externí odkaz:
http://arxiv.org/abs/2311.06013
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 $n$ disks in the plane of arbitrary radii: In this graph two disks are connected if the distance between them is at mo
Externí odkaz:
http://arxiv.org/abs/2307.14663
Let $E=\{e_1,\ldots,e_n\}$ be a set of $C$-oriented disjoint segments in the plane, where $C$ is a given finite set of orientations that spans the plane, and let $s$ and $t$ be two points. %(We also require that for each orientation in $C$, its oppos
Externí odkaz:
http://arxiv.org/abs/2302.06776
Autor:
Katz, Matthew J., Sharir, Micha
We present an algorithm for computing a bottleneck matching in a set of $n=2\ell$ points in the plane, which runs in $O(n^{\omega/2}\log n)$ deterministic time, where $\omega\approx 2.37$ is the exponent of matrix multiplication.
Externí odkaz:
http://arxiv.org/abs/2205.05887
Let $\mathcal{T}$ be a set of $n$ flat (planar) semi-algebraic regions in $\mathbb{R}^3$ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess $\mathcal{T}$ into a data structure so that for a query object $\gam
Externí odkaz:
http://arxiv.org/abs/2203.10241
Autor:
Katz, Matthew J., Sharir, Micha
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 complexity. The common feature of these problems is that they involve
Externí odkaz:
http://arxiv.org/abs/2111.02052
Publikováno v:
In Computational Geometry: Theory and Applications February 2024 117
Autor:
Ashur, Stav, Katz, Matthew J.
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, which have received significant attention. Let $P = \{p_1,\ldots,p_n\}$
Externí odkaz:
http://arxiv.org/abs/2010.11571