33 Search Results for "Agarwal, Pankaj K."

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.6
Facility Location in the Sublinear Geometric Model

Authors: Morteza Monemizadeh

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
In the sublinear geometric model, we are provided with an oracle access to a point set P of n points in a bounded discrete space [Δ]², where Δ = n^O(1) is a polynomially bounded number in n. That is, we do not have direct access to the points, but we can make certain types of queries and there is an oracle that responds to our queries. The type of queries that we assume we can make in this paper, are range counting queries where ranges are axis-aligned rectangles (that are basic primitives in database [Srikanta Tirthapura and David P. Woodruff, 2012; Bentley, 1975; Mark de Berg et al., 2008], computational geometry [Pankaj K. Agarwal, 2004; Pankaj K. Agarwal et al., 1996; Boris Aronov et al., 2010; Boris Aronov et al., 2009], and machine learning [Menachem Sadigurschi and Uri Stemmer, 2021; Long and Tan, 1998; Michael J. Kearns and Umesh V. Vazirani, 1995; Michael J. Kearns and Umesh V. Vazirani, 1994]). The oracle then answers these queries by returning the number of points that are in queried ranges. Let {Alg} be an algorithm that (exactly or approximately) solves a problem 𝒫 in the sublinear geometric model. The query complexity of Alg is measured in terms of the number of queries that Alg makes to solve 𝒫. In this paper, we study the complexity of the (uniform) Euclidean facility location problem in the sublinear geometric model. We develop a randomized sublinear algorithm that with high probability, (1+ε)-approximates the cost of the Euclidean facility location problem of the point set P in the sublinear geometric model using Õ(√n) range counting queries. We complement this result by showing that approximating the cost of the Euclidean facility location problem within o(log(n))-factor in the sublinear geometric model using the sampling strategy that we propose for our sublinear algorithm needs Ω̃(n^{1/4}) RangeCount queries. We leave it as an open problem whether such a polynomial lower bound on the number of RangeCount queries exists for any randomized sublinear algorithm that approximates the cost of the facility location problem within a constant factor.
Cite as

Morteza Monemizadeh. Facility Location in the Sublinear Geometric Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 6:1-6:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{monemizadeh:LIPIcs.APPROX/RANDOM.2023.6,
  author =	{Monemizadeh, Morteza},
  title =	{{Facility Location in the Sublinear Geometric Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  URN =		{urn:nbn:de:0030-drops-188315},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.6},
  annote =	{Keywords: Facility Location, Sublinear Geometric Model, Range Counting Queries}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.7
On Range Summary Queries

Authors: Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter ε and a set P of n points in ℝ^d where each point is assigned a color from a set C, and the goal is to build a structure such that given any geometric range γ, we can efficiently find a list of approximate heavy hitters in γ∩P, i.e., colors that appear at least ε |γ∩P| times in γ∩P, as well as their frequencies with an additive error of ε |γ∩P|. In the latter problem, each point is assigned a weight from a totally ordered universe and the query must output a sequence S of 1+1/ε weights such that the i-th weight in S has approximate rank iε|γ∩P|, meaning, rank iε|γ∩P| up to an additive error of ε|γ∩P|. Previously, optimal results were only known in 1D [Wei and Yi, 2011] but a few sub-optimal methods were available in higher dimensions [Peyman Afshani and Zhewei Wei, 2017; Pankaj K. Agarwal et al., 2012]. We study the problems for two important classes of geometric ranges: 3D halfspace and 3D dominance queries. It is known that many other important queries can be reduced to these two, e.g., 1D interval stabbing or interval containment, 2D three-sided queries, 2D circular as well as 2D k-nearest neighbors queries. We consider the real RAM model of computation where integer registers of size w bits, w = Θ(log n), are also available. For dominance queries, we show optimal solutions for both heavy hitter and quantile problems: using linear space, we can answer both queries in time O(log n + 1/ε). Note that as the output size is 1/ε, after investing the initial O(log n) searching time, our structure takes on average O(1) time to find a heavy hitter or a quantile! For more general halfspace heavy hitter queries, the same optimal query time can be achieved by increasing the space by an extra log_w(1/ε) (resp. log log_w(1/ε)) factor in 3D (resp. 2D). By spending extra log^O(1)(1/ε) factors in both time and space, we can also support quantile queries. We remark that it is hopeless to achieve a similar query bound for dimensions 4 or higher unless significant advances are made in the data structure side of theory of geometric approximations.
Cite as

Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ICALP.2023.7,
  author =	{Afshani, Peyman and Cheng, Pingan and Basu Roy, Aniket and Wei, Zhewei},
  title =	{{On Range Summary Queries}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.7},
  URN =		{urn:nbn:de:0030-drops-180590},
  doi =		{10.4230/LIPIcs.ICALP.2023.7},
  annote =	{Keywords: Computational Geometry, Range Searching, Random Sampling, Geometric Approximation, Data Structures and Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.4
Computing Instance-Optimal Kernels in Two Dimensions

Authors: Pankaj K. Agarwal and Sariel Har-Peled

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Let P be a set of n points in ℝ². For a parameter ε ∈ (0,1), a subset C ⊆ P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (1-ε)-factor in every direction. The set C is a weak ε-kernel of P if its directional width approximates that of P in every direction. Let 𝗄_ε(P) (resp. 𝗄^𝗐_ε(P)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an O(n 𝗄_ε(P)log n)-time algorithm for computing an ε-kernel of P of size 𝗄_ε(P), and an O(n²log n)-time algorithm for computing a weak ε-kernel of P of size 𝗄^𝗐_ε(P). We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of ε-core, a convex polygon lying inside ch(P), prove that it is a good approximation of the optimal ε-kernel, present an efficient algorithm for computing it, and use it to compute an ε-kernel of small size.
Cite as

Pankaj K. Agarwal and Sariel Har-Peled. Computing Instance-Optimal Kernels in Two Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.4,
  author =	{Agarwal, Pankaj K. and Har-Peled, Sariel},
  title =	{{Computing Instance-Optimal Kernels in Two Dimensions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.4},
  URN =		{urn:nbn:de:0030-drops-178544},
  doi =		{10.4230/LIPIcs.SoCG.2023.4},
  annote =	{Keywords: Coreset, approximation, kernel}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.5
Line Intersection Searching Amid Unit Balls in 3-Space

Authors: Pankaj K. Agarwal and Esther Ezra

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Let ℬ be a set of n unit balls in ℝ³. We present a linear-size data structure for storing ℬ that can determine in O^*(n^{1/2}) time whether a query line intersects any ball of ℬ and report all k such balls in additional O(k) time. The data structure can be constructed in O(n log n) time. (The O^*(⋅) notation hides subpolynomial factors, e.g., of the form O(n^ε), for arbitrarily small ε > 0, and their coefficients which depend on ε.) We also consider the dual problem: Let ℒ be a set of n lines in ℝ³. We preprocess ℒ, in O^*(n²) time, into a data structure of size O^*(n²) that can determine in O^*(1) time whether a query unit ball intersects any line of ℒ, or report all k such lines in additional O(k) time.
Cite as

Pankaj K. Agarwal and Esther Ezra. Line Intersection Searching Amid Unit Balls in 3-Space. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 5:1-5:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2023.5,
  author =	{Agarwal, Pankaj K. and Ezra, Esther},
  title =	{{Line Intersection Searching Amid Unit Balls in 3-Space}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.5},
  URN =		{urn:nbn:de:0030-drops-178559},
  doi =		{10.4230/LIPIcs.SoCG.2023.5},
  annote =	{Keywords: Intersection searching, cylindrical range searching, partition trees, union of cylinders}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.35
Multi-Robot Motion Planning for Unit Discs with Revolving Areas

Authors: Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor

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

Abstract
We study the problem of motion planning for a collection of n labeled unit disc robots in a polygonal environment. We assume that the robots have revolving areas around their start and final positions: that each start and each final is contained in a radius 2 disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a weakly-monotone motion plan, in which robots move according to an ordering as follows: during the turn of a robot R in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As R passes through a revolving area, a robot R' that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time (1+ε)-approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an O(1) factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time O(log n log log n)-approximation algorithm for this problem.
Cite as

Pankaj K. Agarwal, Tzvika Geft, Dan Halperin, and Erin Taylor. Multi-Robot Motion Planning for Unit Discs with Revolving Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 35:1-35:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2022.35,
  author =	{Agarwal, Pankaj K. and Geft, Tzvika and Halperin, Dan and Taylor, Erin},
  title =	{{Multi-Robot Motion Planning for Unit Discs with Revolving Areas}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{35:1--35:20},
  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.35},
  URN =		{urn:nbn:de:0030-drops-173204},
  doi =		{10.4230/LIPIcs.ISAAC.2022.35},
  annote =	{Keywords: motion planning, optimal motion planning, approximation, complexity, NP-hardness}
}
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.6
An Improved ε-Approximation Algorithm for Geometric Bipartite Matching

Authors: Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle

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

Abstract
For two point sets A, B ⊂ ℝ^d, with |A| = |B| = n and d > 1 a constant, and for a parameter ε > 0, we present a randomized algorithm that, with probability at least 1/2, computes in O(n(ε^{-O(d³)}log log n + ε^{-O(d)}log⁴ nlog⁵log n)) time, an ε-approximate minimum-cost perfect matching under any L_p-metric. All previous algorithms take n(ε^{-1}log n)^{Ω(d)} time. We use a randomly-shifted tree, with a polynomial branching factor and O(log log n) height, to define a tree-based distance function that ε-approximates the L_p metric as well as to compute the matching hierarchically. Then, we apply the primal-dual framework on a compressed representation of the residual graph to obtain an efficient implementation of the Hungarian-search and augment operations.
Cite as

Pankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle. An Improved ε-Approximation Algorithm for Geometric Bipartite Matching. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 6:1-6:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2022.6,
  author =	{Agarwal, Pankaj K. and Raghvendra, Sharath and Shirzadian, Pouyan and Sowle, Rachita},
  title =	{{An Improved \epsilon-Approximation Algorithm for Geometric Bipartite Matching}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{6:1--6:20},
  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.6},
  URN =		{urn:nbn:de:0030-drops-161660},
  doi =		{10.4230/LIPIcs.SWAT.2022.6},
  annote =	{Keywords: Euclidean bipartite matching, approximation algorithms, primal dual method}
}
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.ITC.2021.18
Differentially Private Approximations of a Convex Hull in Low Dimensions

Authors: Yue Gao and Or Sheffet

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball, etc. Our work relies heavily on the notion of Tukey-depth. Instead of (non-privately) approximating the convex-hull of the given set of points P, our algorithms approximate the geometric features of D_{P}(κ) - the κ-Tukey region induced by P (all points of Tukey-depth κ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature μ our (α,Δ)-approximation is a value "sandwiched" between (1-α)μ(D_P(κ)) and (1+α)μ(D_P(κ-Δ)). Our work is aimed at producing a (α,Δ)-kernel of D_P(κ), namely a set 𝒮 such that (after a shift) it holds that (1-α)D_P(κ) ⊂ CH(𝒮) ⊂ (1+α)D_P(κ-Δ). We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by [Pankaj K. Agarwal et al., 2004], fails to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find (α,Δ)-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn D_P(κ) into a "fat" region but only if its volume is proportional to the volume of D_P(κ-Δ). Lastly, we give a novel private algorithm that finds a depth parameter κ for which the volume of D_P(κ) is comparable to the volume of D_P(κ-Δ). We hope our work leads to the further study of the intersection of differential privacy and computational geometry.
Cite as

Yue Gao and Or Sheffet. Differentially Private Approximations of a Convex Hull in Low Dimensions. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 18:1-18:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ITC.2021.18,
  author =	{Gao, Yue and Sheffet, Or},
  title =	{{Differentially Private Approximations of a Convex Hull in Low Dimensions}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.18},
  URN =		{urn:nbn:de:0030-drops-143377},
  doi =		{10.4230/LIPIcs.ITC.2021.18},
  annote =	{Keywords: Differential Privacy, Computational Geometry, Tukey Depth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.10
An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D

Authors: Pankaj K. Agarwal and Alex Steiger

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ³. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n²). We show that U can be computed in O(n log³ n + κ) time if C is in general position. The algorithm also computes the union of a set of fat boxes (i.e., boxes with bounded aspect ratio) within the same time bound. If the cubes in C are congruent or have bounded depth, the running time improves to O(n log² n), and if both conditions hold, the running time improves to O(n log n).
Cite as

Pankaj K. Agarwal and Alex Steiger. An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2021.10,
  author =	{Agarwal, Pankaj K. and Steiger, Alex},
  title =	{{An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10},
  URN =		{urn:nbn:de:0030-drops-140790},
  doi =		{10.4230/LIPIcs.ICALP.2021.10},
  annote =	{Keywords: union of cubes, fat boxes, plane-sweep}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.11
Dynamic Enumeration of Similarity Joins

Authors: Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, and Jun Yang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This paper considers enumerating answers to similarity-join queries under dynamic updates: Given two sets of n points A,B in ℝ^d, a metric ϕ(⋅), and a distance threshold r > 0, report all pairs of points (a, b) ∈ A × B with ϕ(a,b) ≤ r. Our goal is to store A,B into a dynamic data structure that, whenever asked, can enumerate all result pairs with worst-case delay guarantee, i.e., the time between enumerating two consecutive pairs is bounded. Furthermore, the data structure can be efficiently updated when a point is inserted into or deleted from A or B. We propose several efficient data structures for answering similarity-join queries in low dimension. For exact enumeration of similarity join, we present near-linear-size data structures for 𝓁₁, 𝓁_∞ metrics with log^{O(1)} n update time and delay. We show that such a data structure is not feasible for the 𝓁₂ metric for d ≥ 4. For approximate enumeration of similarity join, where the distance threshold is a soft constraint, we obtain a unified linear-size data structure for 𝓁_p metric, with log^{O(1)} n delay and update time. In high dimensions, we present an efficient data structure with worst-case delay-guarantee using locality sensitive hashing (LSH).
Cite as

Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, and Jun Yang. Dynamic Enumeration of Similarity Joins. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2021.11,
  author =	{Agarwal, Pankaj K. and Hu, Xiao and Sintos, Stavros and Yang, Jun},
  title =	{{Dynamic Enumeration of Similarity Joins}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.11},
  URN =		{urn:nbn:de:0030-drops-140803},
  doi =		{10.4230/LIPIcs.ICALP.2021.11},
  annote =	{Keywords: dynamic enumeration, similarity joins, worst-case delay guarantee}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.12
On Undecided LP, Clustering and Active Learning

Authors: Stav Ashur and Sariel Har-Peled

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) clusters, which are monochromatic (i.e., all the points covered by the same cluster have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various oracle queries (such as nearest neighbor, or separation queries). We show that one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries, if the number of clusters is a constant. We investigate several variants of this problem, including Undecided Linear Programming and covering of points by k monochromatic balls.
Cite as

Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12,
  author =	{Ashur, Stav and Har-Peled, Sariel},
  title =	{{On Undecided LP, Clustering and Active Learning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.12},
  URN =		{urn:nbn:de:0030-drops-138116},
  doi =		{10.4230/LIPIcs.SoCG.2021.12},
  annote =	{Keywords: Linear Programming, Active learning, Classification}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.41
Throwing a Sofa Through the Window

Authors: Dan Halperin, Micha Sharir, and Itay Yehuda

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study several variants of the problem of moving a convex polytope K, with n edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically: ii) We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to O(n^{8/3}). iii) We consider the case of a gate (an unbounded window with two parallel infinite edges), and show that K can pass through such a window, by any collision-free rigid motion, iff it can slide through it, an observation that leads to an efficient algorithm for this variant too. iv) We consider arbitrary compact convex windows, and show that if K can pass through such a window W (by any motion) then K can slide through a slab of width equal to the diameter of W. v) We show that if a purely translational motion for K through a rectangular window W exists, then K can also slide through W keeping the same orientation as in the translational motion. For a given fixed orientation of K we can determine in linear time whether K can translate (and hence slide) through W keeping the given orientation, and if so plan the motion, also in linear time. vi) We give an example of a polytope that cannot pass through a certain window by translations only, but can do so when rotations are allowed. vii) We study the case of a circular window W, and show that, for the regular tetrahedron K of edge length 1, there are two thresholds 1 > δ₁≈ 0.901388 > δ₂≈ 0.895611, such that (a) K can slide through W if the diameter d of W is ≥ 1, (b) K cannot slide through W but can pass through it by a purely translational motion when δ₁ ≤ d < 1, (c) K cannot pass through W by a purely translational motion but can do it when rotations are allowed when δ₂ ≤ d < δ₁, and (d) K cannot pass through W at all when d < δ₂. viii) Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for K through a rectangular window W, and present an efficient algorithm for this problem, with running time close to O(n⁴).
Cite as

Dan Halperin, Micha Sharir, and Itay Yehuda. Throwing a Sofa Through the Window. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 41:1-41:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{halperin_et_al:LIPIcs.SoCG.2021.41,
  author =	{Halperin, Dan and Sharir, Micha and Yehuda, Itay},
  title =	{{Throwing a Sofa Through the Window}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.41},
  URN =		{urn:nbn:de:0030-drops-138409},
  doi =		{10.4230/LIPIcs.SoCG.2021.41},
  annote =	{Keywords: Motion planning, Convex polytopes in 3D}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.8
Clustering Under Perturbation Stability in Near-Linear Time

Authors: Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala, Erin Taylor, and Emo Welzl

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most α. Our main contribution is in presenting efficient exact algorithms for α-stable clustering instances whose running times depend near-linearly on the size of the data set when α ≥ 2 + √3. For k-center and k-means problems, our algorithms also achieve polynomial dependence on the number of clusters, k, when α ≥ 2 + √3 + ε for any constant ε > 0 in any fixed dimension. For k-median, our algorithms have polynomial dependence on k for α > 5 in any fixed dimension; and for α ≥ 2 + √3 in two dimensions. Our algorithms are simple, and only require applying techniques such as local search or dynamic programming to a suitably modified metric space, combined with careful choice of data structures.
Cite as

Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala, Erin Taylor, and Emo Welzl. Clustering Under Perturbation Stability in Near-Linear Time. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 8:1-8:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2020.8,
  author =	{Agarwal, Pankaj K. and Chang, Hsien-Chih and Munagala, Kamesh and Taylor, Erin and Welzl, Emo},
  title =	{{Clustering Under Perturbation Stability in Near-Linear Time}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-132492},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.8},
  annote =	{Keywords: clustering, stability, local search, dynamic programming, coreset, polyhedral metric, trapezoid decomposition, range query}
}
  • Refine by Author
  • 24 Agarwal, Pankaj K.
  • 6 Sharir, Micha
  • 4 Aronov, Boris
  • 4 Katz, Matthew J.
  • 4 Xiao, Allen
  • Show More...

  • Refine by Classification
  • 15 Theory of computation → Computational geometry
  • 7 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 2 Computational Geometry
  • 2 Dynamic data structures
  • 2 Geometric optimization
  • 2 Intersection searching
  • 2 approximation
  • Show More...

  • Refine by Type
  • 33 document

  • Refine by Publication Year
  • 5 2018
  • 5 2021
  • 5 2022
  • 4 2019
  • 4 2023
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact