Search Results

Documents authored by Kumar, Neeraj

Document
DOI: 10.4230/LIPIcs.SoCG.2022.52
Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

Authors: Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue

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

Abstract
Suppose we are given a pair of points s, t and a set 𝒮 of n geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph G with vertex set 𝒮 and every edge labeled from {0, 1}, such that a set 𝒮_d ⊆ 𝒮 of obstacles separates s from t if and only if G[𝒮_d] contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a 2.3146^q n^{O(1)} algorithm for Obstacle-removal, significantly improving upon the previously best known q^{O(q³)} n^{O(1)} algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-separation problem input consists of the set 𝒮 of obstacles, a point set A of k points and p pairs (s₁, t₁), … (s_p, t_p) of points from A. The task is to find a minimum subset 𝒮_r ⊆ 𝒮 such that for every i, every curve from s_i to t_i intersects at least one obstacle in 𝒮_r. We obtain 2^{O(p)} n^{O(k)}-time algorithm for Generalized Points-separation. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where (s₁, t₁), … (s_p, t_p) contains all the pairs of points in A. Finally, we improve the running time of our algorithm to f(p,k) ⋅ n^{O(√k)} when the obstacles are unit disks, where f(p,k) = 2^{O(p)} k^{O(k)}, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on k of our algorithms is essentially optimal.
Cite as

Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri, and Jie Xue. Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.SoCG.2022.52,
  author =	{Kumar, Neeraj and Lokshtanov, Daniel and Saurabh, Saket and Suri, Subhash and Xue, Jie},
  title =	{{Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{52:1--52: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.52},
  URN =		{urn:nbn:de:0030-drops-160609},
  doi =		{10.4230/LIPIcs.SoCG.2022.52},
  annote =	{Keywords: points-separation, min color path, constraint removal, barrier resillience}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.19
The Maximum Exposure Problem

Authors: Neeraj Kumar, Stavros Sintos, and Subhash Suri

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

Abstract
Given a set of points P and axis-aligned rectangles R in the plane, a point p in P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k^2) rectangles, we can expose at least Omega(1/k) of the optimal number of points.
Cite as

Neeraj Kumar, Stavros Sintos, and Subhash Suri. The Maximum Exposure Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.APPROX-RANDOM.2019.19,
  author =	{Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
  title =	{{The Maximum Exposure Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.19},
  URN =		{urn:nbn:de:0030-drops-112344},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.19},
  annote =	{Keywords: max-exposure, PTAS, densest k-subgraphs, geometric constraint removal, Network resilience}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.2
Improved Approximation Bounds for the Minimum Constraint Removal Problem

Authors: Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, and Kasturi Varadarajan

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

Abstract
In the minimum constraint removal problem, we are given a set of geometric objects as obstacles in the plane, and we want to find the minimum number of obstacles that must be removed to reach a target point t from the source point s by an obstacle-free path. The problem is known to be intractable, and (perhaps surprisingly) no sub-linear approximations are known even for simple obstacles such as rectangles and disks. The main result of our paper is a new approximation technique that gives O(sqrt{n})-approximation for rectangles, disks as well as rectilinear polygons. The technique also gives O(sqrt{n})-approximation for the minimum color path problem in graphs. We also present some inapproximability results for the geometric constraint removal problem.
Cite as

Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri, and Kasturi Varadarajan. Improved Approximation Bounds for the Minimum Constraint Removal Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.APPROX-RANDOM.2018.2,
  author =	{Bandyapadhyay, Sayan and Kumar, Neeraj and Suri, Subhash and Varadarajan, Kasturi},
  title =	{{Improved Approximation Bounds for the Minimum Constraint Removal Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.2},
  URN =		{urn:nbn:de:0030-drops-94066},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.2},
  annote =	{Keywords: Minimum Constraint Removal, Minimum Color Path, Barrier Resilience, Obstacle Removal, Obstacle Free Path, Approximation}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.5
Computing Shortest Paths in the Plane with Removable Obstacles

Authors: Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri

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

Abstract
We consider the problem of computing a Euclidean shortest path in the presence of removable obstacles in the plane. In particular, we have a collection of pairwise-disjoint polygonal obstacles, each of which may be removed at some cost c_i > 0. Given a cost budget C > 0, and a pair of points s, t, which obstacles should be removed to minimize the path length from s to t in the remaining workspace? We show that this problem is NP-hard even if the obstacles are vertical line segments. Our main result is a fully-polynomial time approximation scheme (FPTAS) for the case of convex polygons. Specifically, we compute an (1 + epsilon)-approximate shortest path in time O({nh}/{epsilon^2} log n log n/epsilon) with removal cost at most (1+epsilon)C, where h is the number of obstacles, n is the total number of obstacle vertices, and epsilon in (0, 1) is a user-specified parameter. Our approximation scheme also solves a shortest path problem for a stochastic model of obstacles, where each obstacle's presence is an independent event with a known probability. Finally, we also present a data structure that can answer s-t path queries in polylogarithmic time, for any pair of points s, t in the plane.
Cite as

Pankaj K. Agarwal, Neeraj Kumar, Stavros Sintos, and Subhash Suri. Computing Shortest Paths in the Plane with Removable Obstacles. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SWAT.2018.5,
  author =	{Agarwal, Pankaj K. and Kumar, Neeraj and Sintos, Stavros and Suri, Subhash},
  title =	{{Computing Shortest Paths in the Plane with Removable Obstacles}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{5:1--5:15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-88312},
  doi =		{10.4230/LIPIcs.SWAT.2018.5},
  annote =	{Keywords: Euclidean shortest paths, Removable polygonal obstacles, Stochastic shortest paths, L\underline1 shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.49
Shortest Paths in the Plane with Obstacle Violations

Authors: John Hershberger, Neeraj Kumar, and Subhash Suri

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for k <= h. Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of Theta(kn) on the size of this map, and show that it can be computed in O(k^2 n log n) time, where n is the total number of obstacle vertices.
Cite as

John Hershberger, Neeraj Kumar, and Subhash Suri. Shortest Paths in the Plane with Obstacle Violations. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hershberger_et_al:LIPIcs.ESA.2017.49,
  author =	{Hershberger, John and Kumar, Neeraj and Suri, Subhash},
  title =	{{Shortest Paths in the Plane with Obstacle Violations}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.49},
  URN =		{urn:nbn:de:0030-drops-78413},
  doi =		{10.4230/LIPIcs.ESA.2017.49},
  annote =	{Keywords: Shortest paths, Polygonal obstacles, Continuous Dijkstra, Obstacle crossing, Visibility}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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