Search Results

Documents authored by Katz, Matthew

Found 2 Possible Name Variants:

Katz, Matthew J.

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.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}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.6
Network Optimization on Partitioned Pairs of Points

Authors: Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, and Joseph S. B. Mitchell

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Given n pairs of points, S = {{p_1, q_1}, {p_2, q_2}, ..., {p_n, q_n}}, in some metric space, we study the problem of two-coloring the points within each pair, red and blue, to optimize the cost of a pair of node-disjoint networks, one over the red points and one over the blue points. In this paper we consider our network structures to be spanning trees, traveling salesman tours or matchings. We consider several different weight functions computed over the network structures induced, as well as several different objective functions. We show that some of these problems are NP-hard, and provide constant factor approximation algorithms in all cases.
Cite as

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, and Joseph S. B. Mitchell. Network Optimization on Partitioned Pairs of Points. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:LIPIcs.ISAAC.2017.6,
  author =	{Arkin, Esther M. and Banik, Aritra and Carmi, Paz and Citovsky, Gui and Jia, Su and Katz, Matthew J. and Mayer, Tyler and Mitchell, Joseph S. B.},
  title =	{{Network Optimization on Partitioned Pairs of Points}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.6},
  URN =		{urn:nbn:de:0030-drops-82700},
  doi =		{10.4230/LIPIcs.ISAAC.2017.6},
  annote =	{Keywords: Network Optimization, TSP tour, Matching, Spanning Tree, Pairs, Partition, Algorithms, Complexity}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2017
LIPIcs, Volume 77, SoCG'17, Complete Volume

Authors: Boris Aronov and Matthew J. Katz

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
LIPIcs, Volume 77, SoCG'17, Complete Volume
Cite as

33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{aronov_et_al:LIPIcs.SoCG.2017,
  title =	{{LIPIcs, Volume 77, SoCG'17, Complete Volume}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017},
  URN =		{urn:nbn:de:0030-drops-73012},
  doi =		{10.4230/LIPIcs.SoCG.2017},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Nonnumerical Algorithms and Problems – Geometrical problems and computations, Discrete Mathematics}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2017.0
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors

Authors: Boris Aronov and Matthew J. Katz

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
Cite as

33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2017.0,
  author =	{Aronov, Boris and Katz, Matthew J.},
  title =	{{Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.0},
  URN =		{urn:nbn:de:0030-drops-71770},
  doi =		{10.4230/LIPIcs.SoCG.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.37
On the General Chain Pair Simplification Problem

Authors: Chenglin Fan, Omrit Filtser, Matthew J. Katz, and Binhai Zhu

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated by the problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones. In this problem, given two polygonal chains of lengths n and m, the goal is to simplify both of them simultaneously, so that the lengths of the resulting simplifications as well as the discrete Frechet distance between them are bounded. When the vertices of the simplifications are arbitrary (i.e., not necessarily from the original chains), the problem is called General CPS (GCPS). In this paper we consider for the first time the complexity of GCPS under both the discrete Frechet distance (GCPS-3F) and the Hausdorff distance (GCPS-2H). (In the former version, the quality of the two simplifications is measured by the discrete Fr'echet distance, and in the latter version it is measured by the Hausdorff distance.) We prove that GCPS-3F is polynomially solvable, by presenting an widetilde-O((n+m)^6 min{n,m}) time algorithm for the corresponding minimization problem. We also present an O((n+m)^4) 2-approximation algorithm for the problem. On the other hand, we show that GCPS-2H is NP-complete, and present an approximation algorithm for the problem.
Cite as

Chenglin Fan, Omrit Filtser, Matthew J. Katz, and Binhai Zhu. On the General Chain Pair Simplification Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fan_et_al:LIPIcs.MFCS.2016.37,
  author =	{Fan, Chenglin and Filtser, Omrit and Katz, Matthew J. and Zhu, Binhai},
  title =	{{On the General Chain Pair Simplification Problem}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.37},
  URN =		{urn:nbn:de:0030-drops-64510},
  doi =		{10.4230/LIPIcs.MFCS.2016.37},
  annote =	{Keywords: chain simplification, discrete Frechet distance, dynamic programming, geometric arrangements, protein structural resemblance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.34
On Interference Among Moving Sensors and Related Problems

Authors: Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, and Shakhar Smorodinsky

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We show that for any set of n moving points in R^d and any parameter 2<=k<n, one can select a fixed non-empty subset of the points of size O(k log k), such that the Voronoi diagram of this subset is "balanced" at any given time (i.e., it contains O(n/k) points per cell). We also show that the bound O(k log k) is near optimal even for the one dimensional case in which points move linearly in time. As an application, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time, their interference is O( (n log n)^0.5). This is optimal up to an O((log n)^0.5) factor.
Cite as

Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, and Shakhar Smorodinsky. On Interference Among Moving Sensors and Related Problems. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.ESA.2016.34,
  author =	{De Carufel, Jean-Lou and Katz, Matthew J. and Korman, Matias and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Smorodinsky, Shakhar},
  title =	{{On Interference Among Moving Sensors and Related Problems}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.34},
  URN =		{urn:nbn:de:0030-drops-63850},
  doi =		{10.4230/LIPIcs.ESA.2016.34},
  annote =	{Keywords: Range spaces, Voronoi diagrams, moving points, facility location, interference minimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.25
Locating Battery Charging Stations to Facilitate Almost Shortest Paths

Authors: Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.
Cite as

Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal. Locating Battery Charging Stations to Facilitate Almost Shortest Paths. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 25-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:OASIcs.ATMOS.2014.25,
  author =	{Arkin, Esther M. and Carmi, Paz and Katz, Matthew J. and Mitchell, Joseph S. B. and Segal, Michael},
  title =	{{Locating Battery Charging Stations to Facilitate Almost Shortest Paths}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{25--33},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.25},
  URN =		{urn:nbn:de:0030-drops-47500},
  doi =		{10.4230/OASIcs.ATMOS.2014.25},
  annote =	{Keywords: approximation algorithms; geometric spanners; transportation networks}
}

Katz, Matthew

Document
DOI: 10.4230/DagSemProc.06481.3
Power Assignment in Radio Networks with Two Power Levels

Authors: Paz Carmi and Matthew Katz

Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

Abstract
We study the power assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges - short and long. We show that this problem is NP-hard, and present an O(n^2)-time assignment algorithm, such that the number of transmitters that are assigned long range by the algorithm is at most (11/6) times the number of transmitters that are assigned long range by an optimal algorithm. We also present an (9/5)-approximation algorithm for this problem whose running time is considerably higher. Next, we formulate and study the Minimum-Area Spanning Tree (MAST)problem: Given a set P of n points in the plane, find a spanning tree of P of minimum "area," where the area of a spanning tree T is the area of the union of the n-1 disks whose diameters are the edges in T. We prove that the Euclidean minimum spanning tree of P is a constant-factor approximation for MAST. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (MARA) problem, for the Minimum-Area Connected Disk Graph (MACDG) problem, and for the Minimum-Area Tour (MAT) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.
Cite as

Paz Carmi and Matthew Katz. Power Assignment in Radio Networks with Two Power Levels. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{carmi_et_al:DagSemProc.06481.3,
  author =	{Carmi, Paz and Katz, Matthew},
  title =	{{Power Assignment in Radio Networks with Two Power Levels}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.3},
  URN =		{urn:nbn:de:0030-drops-10277},
  doi =		{10.4230/DagSemProc.06481.3},
  annote =	{Keywords: Radio networks, power assignment, approximation algorithms, minimum spanning tree, disk graph}
}
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 Imprint Privacy Contact