89 Search Results for "Katz, Matthew J."

Volume

LIPIcs, Volume 77

33rd International Symposium on Computational Geometry (SoCG 2017)

SoCG 2017, July 4-7, 2017, Brisbane, Australia

Editors: Boris Aronov and Matthew J. Katz

Document
DOI: 10.4230/LIPIcs.ESA.2024.7
Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments

Authors: Pankaj K. Agarwal, Haim Kaplan, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In this paper we study a few proximity problems related to a set of pairwise-disjoint segments in {ℝ}². Let S be a set of n pairwise-disjoint segments in {ℝ}², and let r > 0 be a parameter. We define the segment proximity graph of S to be G_r(S) := (S,E), where E = {(e₁,e₂) ∣ dist(e₁,e₂) ≤ r} and dist (e₁,e₂) = min_{(p,q) ∈ e₁× e₂} ‖p-q‖ is the Euclidean distance between e₁ and e₂. We define the weight of an edge (e₁,e₂) ∈ E to be dist(e₁,e₂). We first present a simple grid-based O(nlog² n)-time algorithm for computing a BFS tree of G_r(S). We apply it to obtain an O^*(n^{6/5}) + O(nlog²nlogΔ)-time algorithm for the so-called reverse shortest path problem, in which we want to find the smallest value r^* for which G_{r^*}(S) contains a path of some specified length between two designated start and target segments (where the O^*(⋅) notation hides polylogarithmic factors). Here Δ = max_{e ≠ e' ∈ S} dist(e,e')/min_{e ≠ e' ∈ S} dist(e,e') is the spread of S. Next, we present a dynamic data structure that can maintain a set S of pairwise-disjoint segments in the plane under insertions/deletions, so that, for a query segment e from an unknown set Q of pairwise-disjoint segments, such that e does not intersect any segment in (the current version of) S, the segment of S closest to e can be computed in O(log⁵ n) amortized time. The amortized update time is also O(log⁵ n). We note that if the segments in S∪Q are allowed to intersect then the known lower bounds on halfplane range searching suggest that a sequence of n updates and queries may take at least close to Ω(n^{4/3}) time. One thus has to strongly rely on the non-intersecting property of S and Q to perform updates and queries in O(polylog(n)) (amortized) time each. Using these results on nearest-neighbor (NN) searching for disjoint segments, we show that a DFS tree (or forest) of G_r(S) can be computed in O^*(n) time. We also obtain an O^*(n)-time algorithm for constructing a minimum spanning tree of G_r(S). Finally, we present an O^*(n^{4/3})-time algorithm for computing a single-source shortest-path tree in G_r(S). This is the only result that does not exploit the disjointness of the input segments.
Cite as

Pankaj K. Agarwal, Haim Kaplan, Matthew J. Katz, and Micha Sharir. Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ESA.2024.7,
  author =	{Agarwal, Pankaj K. and Kaplan, Haim and Katz, Matthew J. and Sharir, Micha},
  title =	{{Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.7},
  URN =		{urn:nbn:de:0030-drops-210782},
  doi =		{10.4230/LIPIcs.ESA.2024.7},
  annote =	{Keywords: segment proximity graphs, nearest neighbor searching, dynamic data structures, BFS, DFS, unit-disk graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.77
Near-Linear Algorithms for Visibility Graphs over a 1.5-Dimensional Terrain

Authors: Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We present several near-linear algorithms for problems involving visibility over a 1.5-dimensional terrain. Concretely, we have a 1.5-dimensional terrain T, i.e., a bounded x-monotone polygonal path in the plane, with n vertices, and a set P of m points that lie on or above T. The visibility graph VG(P,T) is the graph with P as its vertex set and {(p,q) | p and q are visible to each other} as its edge set. We present algorithms that perform BFS and DFS on VG(P,T), which run in O(nlog n + mlog³(m+n)) time. We also consider three optimization problems, in which P is a set of points on T, and we erect a vertical tower of height h at each p ∈ P. In the first problem, called the reverse shortest path problem, we are given two points s, t ∈ P, and an integer k, and wish to find the smallest height h^* for which VG(P(h^*),T) contains a path from s to t of at most k edges, where P(h^*) is the set of the tips of the towers of height h^* erected at the points of P. In the second problem we wish to find the smallest height h^* for which VG(P(h^*),T) contains a cycle, and in the third problem we wish to find the smallest height h^* for which VG(P(h^*),T) is nonempty; we refer to that problem as "Seeing the most without being seen". We present algorithms for the first two problems that run in O^*((m+n)^{6/5}) time, where the O^*(⋅) notation hides subpolynomial factors. The third problem can be solved by a faster algorithm, which runs in O((n+m)log³ (m+n)) time.
Cite as

Matthew J. Katz, Rachel Saban, and Micha Sharir. Near-Linear Algorithms for Visibility Graphs over a 1.5-Dimensional Terrain. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{katz_et_al:LIPIcs.ESA.2024.77,
  author =	{Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{Near-Linear Algorithms for Visibility Graphs over a 1.5-Dimensional Terrain}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.77},
  URN =		{urn:nbn:de:0030-drops-211482},
  doi =		{10.4230/LIPIcs.ESA.2024.77},
  annote =	{Keywords: 1.5-dimensional terrain, visibility, visibility graph, reverse shortest path, parametric search, shrink-and-bifurcate, range searching}
}
Document
DOI: 10.4230/LIPIcs.ITP.2024.4
Taming Differentiable Logics with Coq Formalisation

Authors: Reynald Affeldt, Alessandro Bruni, Ekaterina Komendantskaya, Natalia Ślusarz, and Kathrin Stark

Published in: LIPIcs, Volume 309, 15th International Conference on Interactive Theorem Proving (ITP 2024)

Abstract
For performance and verification in machine learning, new methods have recently been proposed that optimise learning systems to satisfy formally expressed logical properties. Among these methods, differentiable logics (DLs) are used to translate propositional or first-order formulae into loss functions deployed for optimisation in machine learning. At the same time, recent attempts to give programming language support for verification of neural networks showed that DLs can be used to compile verification properties to machine-learning backends. This situation is calling for stronger guarantees about the soundness of such compilers, the soundness and compositionality of DLs, and the differentiability and performance of the resulting loss functions. In this paper, we propose an approach to formalise existing DLs using the Mathematical Components library in the Coq proof assistant. Thanks to this formalisation, we are able to give uniform semantics to otherwise disparate DLs, give formal proofs to existing informal arguments, find errors in previous work, and provide formal proofs to missing conjectured properties. This work is meant as a stepping stone for the development of programming language support for verification of machine learning.
Cite as

Reynald Affeldt, Alessandro Bruni, Ekaterina Komendantskaya, Natalia Ślusarz, and Kathrin Stark. Taming Differentiable Logics with Coq Formalisation. In 15th International Conference on Interactive Theorem Proving (ITP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 309, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{affeldt_et_al:LIPIcs.ITP.2024.4,
  author =	{Affeldt, Reynald and Bruni, Alessandro and Komendantskaya, Ekaterina and \'{S}lusarz, Natalia and Stark, Kathrin},
  title =	{{Taming Differentiable Logics with Coq Formalisation}},
  booktitle =	{15th International Conference on Interactive Theorem Proving (ITP 2024)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-337-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{309},
  editor =	{Bertot, Yves and Kutsia, Temur and Norrish, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.4},
  URN =		{urn:nbn:de:0030-drops-207325},
  doi =		{10.4230/LIPIcs.ITP.2024.4},
  annote =	{Keywords: Machine Learning, Loss Functions, Differentiable Logics, Logic and Semantics, Interactive Theorem Proving}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.10
Discrete Fréchet Distance Oracles

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
It is unlikely that the discrete Fréchet 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 data structures (distance oracles) of near-linear size that support efficient distance queries with respect to P in sublinear time. Since there is evidence that this is impossible for query curves of length Θ(n^α), for any α > 0, we focus on query curves of (small) constant length, for which we are able to devise distance oracles with the desired bounds. We extend our tools to handle subcurves of the given curve, and even arbitrary vertex-to-vertex subcurves of a given geometric tree. That is, we construct an oracle that can quickly compute the distance between a short polygonal path (the query) and a path in the preprocessed tree between two query-specified vertices. Moreover, we define a new family of geometric graphs, t-local graphs (which strictly contains the family of geometric spanners with constant stretch), for which a similar oracle exists: we can preprocess a graph G in the family, so that, given a query segment and a pair u,v of vertices in G, one can quickly compute the smallest discrete Fréchet distance between the segment and any (u,v)-path in G. The answer is exact, if t = 1, and approximate if t > 1.
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. Discrete Fréchet Distance Oracles. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2024.10,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{Discrete Fr\'{e}chet Distance Oracles}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.10},
  URN =		{urn:nbn:de:0030-drops-199554},
  doi =		{10.4230/LIPIcs.SoCG.2024.10},
  annote =	{Keywords: discrete Fr\'{e}chet distance, distance oracle, heavy-path decomposition, t-local graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.47
Robustly Guarding Polygons

Authors: Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
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, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.
Cite as

Rathish Das, Omrit Filtser, Matthew J. Katz, and Joseph S.B. Mitchell. Robustly Guarding Polygons. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.SoCG.2024.47,
  author =	{Das, Rathish and Filtser, Omrit and Katz, Matthew J. and Mitchell, Joseph S.B.},
  title =	{{Robustly Guarding Polygons}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.47},
  URN =		{urn:nbn:de:0030-drops-199928},
  doi =		{10.4230/LIPIcs.SoCG.2024.47},
  annote =	{Keywords: geometric optimization, approximation algorithms, guarding}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.67
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Authors: Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
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 most some threshold parameter r. The case of intersection graphs is a special case with r = 0. We give an algorithm that, given a target length k, computes the smallest value of r for which there is a path of length at most k between some given pair of disks in the proximity graph. Our algorithm runs in O^*(n^{5/4}) randomized expected time, which improves to O^*(n^{6/5}) for unit disk graphs, where all the disks have the same radius. Our technique is robust and can be applied to many variants of the problem. One significant variant is the case of weighted proximity graphs, where edges are assigned real weights equal to the distance between the disks or between their centers, and k is replaced by a target weight w. In other variants, we want to optimize a parameter different from r, such as a scale factor of the radii of the disks. The main technique for the decision version of the problem (determining whether the graph with a given r has the desired property) is based on efficient implementations of BFS (for the unweighted case) and of Dijkstra’s algorithm (for the weighted case), using efficient data structures for maintaining the bichromatic closest pair for certain bicliques and several distance functions. The optimization problem is then solved by combining the resulting decision procedure with enhanced variants of the interval shrinking and bifurcation technique of [R. Ben Avraham et al., 2015].
Cite as

Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir. The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2023.67,
  author =	{Kaplan, Haim and Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.67},
  URN =		{urn:nbn:de:0030-drops-187208},
  doi =		{10.4230/LIPIcs.ESA.2023.67},
  annote =	{Keywords: Computational geometry, geometric optimization, disk graphs, BFS, Dijkstra’s algorithm, reverse shortest path}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.42
On Reverse Shortest Paths in Geometric Proximity Graphs

Authors: Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in ℝ², and let ϱ: S× S → ℝ_{≥ 0} be a distance function on S. For a parameter r ≥ 0, we define the proximity graph G(r) = (S,E) where E = {(e₁,e₂) ∈ S×S ∣ e₁≠e₂, ϱ(e₁,e₂) ≤ r}. Given S, s,t ∈ S, and an integer k ≥ 1, the reverse-shortest-path (RSP) problem asks for computing the smallest value r^* ≥ 0 such that G(r^*) contains a path from s to t of length at most k. In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0, determine whether G(r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r^*, by efficiently performing a binary search over an implicit set of O(n²) candidate values that contains r^*. We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O^*(n^{4/3}) expected-time randomized algorithm (where O^*(⋅) hides polylog(n) factors) for the case where S is a set of pairwise-disjoint line segments in ℝ² and ϱ(e₁,e₂) = min_{x ∈ e₁, y ∈ e₂} ‖x-y‖ (where ‖⋅‖ is the Euclidean distance), and (ii) an O^*(n+m^{4/3}) expected-time randomized algorithm for the case where S is a set of m points lying on an x-monotone polygonal chain T with n vertices, and ϱ(p,q), for p,q ∈ S, is the smallest value h such that the points p' := p+(0,h) and q' := q+(0,h) are visible to each other, i.e., all points on the segment p'q' lie above or on the polygonal chain T.
Cite as

Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. On Reverse Shortest Paths in Geometric Proximity Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.42,
  author =	{Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
  title =	{{On Reverse Shortest Paths in Geometric Proximity Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.42},
  URN =		{urn:nbn:de:0030-drops-173277},
  doi =		{10.4230/LIPIcs.ISAAC.2022.42},
  annote =	{Keywords: Geometric optimization, proximity graphs, semi-algebraic range searching, reverse shortest path}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.11
Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors

Authors: Boris Aronov and Matthew J. Katz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time. The approach works not only for the Euclidean norm, but for other norms in ℝ^d, for any fixed d. We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art. To obtain the latter result, we needed a data structure for dynamic approximate halfplane range counting in the plane. Since we could not find such a data structure in the literature, we also show how to dynamize one of the known static data structures.
Cite as

Boris Aronov and Matthew J. Katz. Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SWAT.2022.11,
  author =	{Aronov, Boris and Katz, Matthew J.},
  title =	{{Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.11},
  URN =		{urn:nbn:de:0030-drops-161710},
  doi =		{10.4230/LIPIcs.SWAT.2022.11},
  annote =	{Keywords: Nearest neighbors, Approximate nearest neighbors, Weighted nearest neighbors, Nearest neighbor queries, SINR queries, Dynamic data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.4
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

Authors: Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Let 𝒯 be a set of n planar semi-algebraic regions in ℝ³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess 𝒯 into a data structure so that for a query object γ, which is also a plate, we can quickly answer various intersection queries, such as detecting whether γ intersects any plate of 𝒯, reporting all the plates intersected by γ, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in ℝ³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in ℝ³. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if 𝒯 is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^{4/3}) storage (where the O^*(⋅) notation hides subpolynomial factors) and answers an intersection query in O^*(n^{2/3}) time. Alternatively, by increasing the storage to O^*(n^{3/2}), the query time can be decreased to O^*(n^{ρ}), where ρ = (2t-3)/3(t-1) < 2/3 and t ≥ 3 is the number of parameters needed to represent the query arcs.
Cite as

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, and Micha Sharir. Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2022.4,
  author =	{Agarwal, Pankaj K. and Aronov, Boris and Ezra, Esther and Katz, Matthew J. and Sharir, Micha},
  title =	{{Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.4},
  URN =		{urn:nbn:de:0030-drops-160126},
  doi =		{10.4230/LIPIcs.SoCG.2022.4},
  annote =	{Keywords: Intersection searching, Semi-algebraic range searching, Point-enclosure queries, Ray-shooting queries, Polynomial partitions, Cylindrical algebraic decomposition, Multi-level partition trees, Collision detection}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.9
Dynamic Time Warping-Based Proximity Problems

Authors: Boris Aronov, Matthew J. Katz, and Elad Sulami

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Dynamic Time Warping (DTW) is a well-known similarity measure for curves, i.e., sequences of points, and especially for time series. We study several proximity problems for curves, where dynamic time warping is the underlying similarity measure. More precisely, we focus on the variants of these problems, in which, whenever we refer to the dynamic time warping distance between two curves, one of them is a line segment (i.e., a sequence of length two). These variants already reveal some of the difficulties that occur when dealing with the more general ones. Specifically, we study the following three problems: (i) distance oracle: given a curve C in ℝ^d, preprocess it to accommodate distance computations between query segments and C, (ii) segment center: given a set 𝒞 of curves in ℝ^d, find a segment s that minimizes the maximum distance between s and a curve in 𝒞, and (iii) segment nearest neighbor: given 𝒞, construct a data structure for segment nearest neighbor queries, i.e., return the curve in 𝒞 which is closest to a query segment s. We present solutions to these problems in any constant dimension d ≥ 1, using L_∞ for inter-point distances. We also consider the approximation version of the first problem, using L₁ for inter-point distances. That is, given a length-m curve C in ℝ^d, we construct a data structure of size O(m log m) that allows one to compute a 2-approximation of the distance between a query segment s and C in O(log³ m) time. Finally, we describe an interesting experimental study that we performed, which is related to the first problem above.
Cite as

Boris Aronov, Matthew J. Katz, and Elad Sulami. Dynamic Time Warping-Based Proximity Problems. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.MFCS.2020.9,
  author =	{Aronov, Boris and Katz, Matthew J. and Sulami, Elad},
  title =	{{Dynamic Time Warping-Based Proximity Problems}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.9},
  URN =		{urn:nbn:de:0030-drops-126794},
  doi =		{10.4230/LIPIcs.MFCS.2020.9},
  annote =	{Keywords: dynamic time warping, distance oracle, clustering, nearest-neighbor search}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.48
Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic

Authors: Arnold Filtser, Omrit Filtser, and Matthew J. Katz

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In the (1+ε,r)-approximate near-neighbor problem for curves (ANNC) under some similarity measure δ, the goal is to construct a data structure for a given set 𝒞 of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ 𝒞 such that δ(Q,C)≤ r, then return a curve C' ∈ 𝒞 with δ(Q,C') ≤ (1+ε)r. There exists an efficient reduction from the (1+ε)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ 𝒞 with δ(Q,C) ≤ (1+ε)⋅δ(Q,C^*), where C^* is the curve of 𝒞 most similar to Q. Given a set 𝒞 of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n⋅ O(1/ε)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.
Cite as

Arnold Filtser, Omrit Filtser, and Matthew J. Katz. Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.ICALP.2020.48,
  author =	{Filtser, Arnold and Filtser, Omrit and Katz, Matthew J.},
  title =	{{Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{48:1--48:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.48},
  URN =		{urn:nbn:de:0030-drops-124555},
  doi =		{10.4230/LIPIcs.ICALP.2020.48},
  annote =	{Keywords: polygonal curves, Fr\'{e}chet distance, dynamic time warping, approximation algorithms, (asymmetric) approximate nearest neighbor, range counting}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.8
Bipartite Diameter and Other Measures Under Translation

Authors: Boris Aronov, Omrit Filtser, Matthew J. Katz, and Khadijeh Sheikhan

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Let A and B be two sets of points in R^d, where |A|=|B|=n and the distance between them is defined by some bipartite measure dist(A, B). We study several problems in which the goal is to translate the set B, so that dist(A, B) is minimized. The main measures that we consider are (i) the diameter in two and three dimensions, that is diam(A,B) = max {d(a,b) | a in A, b in B}, where d(a,b) is the Euclidean distance between a and b, (ii) the uniformity in the plane, that is uni(A,B) = diam(A,B) - d(A,B), where d(A,B)=min{d(a,b) | a in A, b in B}, and (iii) the union width in two and three dimensions, that is union_width(A,B) = width(A cup B). For each of these measures we present efficient algorithms for finding a translation of B that minimizes the distance: For diameter we present near-linear-time algorithms in R^2 and R^3, for uniformity we describe a roughly O(n^{9/4})-time algorithm, and for union width we offer a near-linear-time algorithm in R^2 and a quadratic-time one in R^3.
Cite as

Boris Aronov, Omrit Filtser, Matthew J. Katz, and Khadijeh Sheikhan. Bipartite Diameter and Other Measures Under Translation. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.STACS.2019.8,
  author =	{Aronov, Boris and Filtser, Omrit and Katz, Matthew J. and Sheikhan, Khadijeh},
  title =	{{Bipartite Diameter and Other Measures Under Translation}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.8},
  URN =		{urn:nbn:de:0030-drops-102476},
  doi =		{10.4230/LIPIcs.STACS.2019.8},
  annote =	{Keywords: Translation-invariant similarity measures, Geometric optimization, Minimum-width annulus}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.145
Resolving SINR Queries in a Dynamic Setting

Authors: Boris Aronov, Gali Bar-On, and Matthew J. Katz

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider a set of transmitters broadcasting simultaneously on the same frequency under the SINR model. Transmission power may vary from one transmitter to another, and a signal's strength decreases (path loss or path attenuation) by some constant power alpha of the distance traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger than the signal of all other transmitters, combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite yes or definite no, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either yes or no. We describe several compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where both queries and updates (insertion or deletion of a transmitter) can be performed efficiently.
Cite as

Boris Aronov, Gali Bar-On, and Matthew J. Katz. Resolving SINR Queries in a Dynamic Setting. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ICALP.2018.145,
  author =	{Aronov, Boris and Bar-On, Gali and Katz, Matthew J.},
  title =	{{Resolving SINR Queries in a Dynamic Setting}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{145:1--145:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.145},
  URN =		{urn:nbn:de:0030-drops-91495},
  doi =		{10.4230/LIPIcs.ICALP.2018.145},
  annote =	{Keywords: Wireless networks, SINR, dynamic insertion and deletion, interference cancellation, range searching}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.20
Algorithms for the Discrete Fréchet Distance Under Translation

Authors: Omrit Filtser and Matthew J. Katz

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
The (discrete) Fréchet distance (DFD) is a popular similarity measure for curves. Often the input curves are not aligned, so one of them must undergo some transformation for the distance computation to be meaningful. Ben Avraham et al. [Rinat Ben Avraham et al., 2015] presented an O(m^3n^2(1+log(n/m))log(m+n))-time algorithm for DFD between two sequences of points of sizes m and n in the plane under translation. In this paper we consider two variants of DFD, both under translation. For DFD with shortcuts in the plane, we present an O(m^2n^2 log^2(m+n))-time algorithm, by presenting a dynamic data structure for reachability queries in the underlying directed graph. In 1D, we show how to avoid the use of parametric search and remove a logarithmic factor from the running time of (the 1D versions of) these algorithms and of an algorithm for the weak discrete Fréchet distance; the resulting running times are thus O(m^2n(1+log(n/m))), for the discrete Fréchet distance, and O(mn log(m+n)), for its two variants. Our 1D algorithms follow a general scheme introduced by Martello et al. [Martello et al., 1984] for the Balanced Optimization Problem (BOP), which is especially useful when an efficient dynamic version of the feasibility decider is available. We present an alternative scheme for BOP, whose advantage is that it yields efficient algorithms quite easily, without having to devise a specially tailored dynamic version of the feasibility decider. We demonstrate our scheme on the most uniform path problem (significantly improving the known bound), and observe that the weak DFD under translation in 1D is a special case of it.
Cite as

Omrit Filtser and Matthew J. Katz. Algorithms for the Discrete Fréchet Distance Under Translation. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SWAT.2018.20,
  author =	{Filtser, Omrit and Katz, Matthew J.},
  title =	{{Algorithms for the Discrete Fr\'{e}chet Distance Under Translation}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.20},
  URN =		{urn:nbn:de:0030-drops-88466},
  doi =		{10.4230/LIPIcs.SWAT.2018.20},
  annote =	{Keywords: curve similarity, discrete Fr\'{e}chet distance, translation, algorithms, BOP}
}
  • Refine by Author
  • 19 Katz, Matthew J.
  • 8 Aronov, Boris
  • 7 Sharir, Micha
  • 5 Filtser, Omrit
  • 4 Abrahamsen, Mikkel
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 5 approximation algorithms
  • 5 computational geometry
  • 5 range searching
  • 3 art gallery problem
  • 3 clustering
  • Show More...

  • Refine by Type
  • 88 document
  • 1 volume

  • Refine by Publication Year
  • 72 2017
  • 5 2024
  • 3 2022
  • 2 2016
  • 2 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact