Search Results

Documents authored by Raman, Rajiv

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.53
A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles

Authors: Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
For a hypergraph ℋ = (X,ℰ) a support is a graph G on X such that for each E ∈ ℰ, the induced subgraph of G on the elements in E is connected. If G is planar, we call it a planar support. A set of axis parallel rectangles ℛ forms a non-piercing family if for any R₁, R₂ ∈ ℛ, R₁⧵R₂ is connected. Given a set P of n points in ℝ² and a set ℛ of m non-piercing axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph (P,ℛ) in O(nlog² n + (n+m)log m) time, where each R ∈ ℛ defines a hyperedge consisting of all points of P contained in R.
Cite as

Ambar Pal, Rajiv Raman, Saurabh Ray, and Karamjeet Singh. A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pal_et_al:LIPIcs.ISAAC.2024.53,
  author =	{Pal, Ambar and Raman, Rajiv and Ray, Saurabh and Singh, Karamjeet},
  title =	{{A Fast Algorithm for Computing a Planar Support for Non-Piercing Rectangles}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{53:1--53:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.53},
  URN =		{urn:nbn:de:0030-drops-221819},
  doi =		{10.4230/LIPIcs.ISAAC.2024.53},
  annote =	{Keywords: Algorithms, Hypergraphs, Computational Geometry, Visualization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.45
Sweeping Arrangements of Non-Piercing Regions in the Plane

Authors: Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray

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

Abstract
Let Γ be a finite set of Jordan curves in the plane. For any curve γ ∈ Γ, we denote the bounded region enclosed by γ as γ̃. We say that Γ is a non-piercing family if for any two curves α , β ∈ Γ, α̃ ⧵ β̃ is a connected region. A non-piercing family of curves generalizes a family of 2-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger ("Sweeping Arrangements of Curves", SoCG '89) proved that if we are given a family Γ of 2-intersecting curves and a sweep curve γ ∈ Γ, then the arrangement can be swept by γ while always maintaining the 2-intersecting property of the curves. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing curves. We show that given an arrangement of non-piercing curves Γ, and a sweep curve γ ∈ Γ, the arrangement can be swept by γ so that the arrangement remains non-piercing throughout the process. We also give a shorter and simpler proof of the result of Snoeyink and Hershberger, and give an eclectic set of applications.
Cite as

Suryendu Dalal, Rahul Gangopadhyay, Rajiv Raman, and Saurabh Ray. Sweeping Arrangements of Non-Piercing Regions in the Plane. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalal_et_al:LIPIcs.SoCG.2024.45,
  author =	{Dalal, Suryendu and Gangopadhyay, Rahul and Raman, Rajiv and Ray, Saurabh},
  title =	{{Sweeping Arrangements of Non-Piercing Regions in the Plane}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{45:1--45:15},
  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.45},
  URN =		{urn:nbn:de:0030-drops-199900},
  doi =		{10.4230/LIPIcs.SoCG.2024.45},
  annote =	{Keywords: Sweeping, Pseudodisks, Discrete Geometry, Topology}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.12
On Geometric Priority Set Cover Problems

Authors: Aritra Banik, Rajiv Raman, and Saurabh Ray

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane.
Cite as

Aritra Banik, Rajiv Raman, and Saurabh Ray. On Geometric Priority Set Cover Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{banik_et_al:LIPIcs.ISAAC.2021.12,
  author =	{Banik, Aritra and Raman, Rajiv and Ray, Saurabh},
  title =	{{On Geometric Priority Set Cover Problems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.12},
  URN =		{urn:nbn:de:0030-drops-154459},
  doi =		{10.4230/LIPIcs.ISAAC.2021.12},
  annote =	{Keywords: Approximation algorithms, geometric set cover, local search, quasi-uniform sampling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.78
Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions

Authors: Rajiv Raman and Saurabh Ray

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
In the Set Multicover problem, we are given a set system (X,𝒮), where X is a finite ground set, and 𝒮 is a collection of subsets of X. Each element x ∈ X has a non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection 𝒮' of 𝒮 such that each point is covered by at least d(x) sets from 𝒮'. In this paper, we study the set multicover problem for set systems defined by points and non-piercing regions in the plane, which includes disks, pseudodisks, k-admissible regions, squares, unit height rectangles, homothets of convex sets, upward paths on a tree, etc. We give a polynomial time (2+ε)-approximation algorithm for the set multicover problem (P, ℛ), where P is a set of points with demands, and ℛ is a set of non-piercing regions, as well as for the set multicover problem (𝒟, P), where 𝒟 is a set of pseudodisks with demands, and P is a set of points in the plane, which is the hitting set problem with demands.
Cite as

Rajiv Raman and Saurabh Ray. Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.ESA.2020.78,
  author =	{Raman, Rajiv and Ray, Saurabh},
  title =	{{Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{78:1--78:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.78},
  URN =		{urn:nbn:de:0030-drops-129441},
  doi =		{10.4230/LIPIcs.ESA.2020.78},
  annote =	{Keywords: Approximation algorithms, geometry, Covering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.69
Planar Support for Non-piercing Regions and Applications

Authors: Rajiv Raman and Saurabh Ray

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Given a hypergraph H=(X,S), a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S in S, the sub-graph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraph H_R(B) = (B, {B_r}_{r in R}), where B_r = {b in B: b cap r != empty set} has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R cup B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.
Cite as

Rajiv Raman and Saurabh Ray. Planar Support for Non-piercing Regions and Applications. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{raman_et_al:LIPIcs.ESA.2018.69,
  author =	{Raman, Rajiv and Ray, Saurabh},
  title =	{{Planar Support for Non-piercing Regions and Applications}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.69},
  URN =		{urn:nbn:de:0030-drops-95320},
  doi =		{10.4230/LIPIcs.ESA.2018.69},
  annote =	{Keywords: Geometric optimization, packing and covering, non-piercing regions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.47
Packing and Covering with Non-Piercing Regions

Authors: Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy

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

Abstract
In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). We show that the local search algorithm that yields PTASs when the regions are disks [Aschner/Katz/Morgenstern/Yuditsky, WALCOM 2013; Gibson/Pirwani, 2005; Mustafa/Raman/Ray, 2015] can be extended to work for non-piercing regions. While such an extension is intuitive and natural, attempts to settle this question have failed even for pseudodisks. The techniques used for analysis when the regions are disks rely heavily on the underlying geometry, and do not extend to topologically defined settings such as pseudodisks. In order to prove our results, we introduce novel techniques that we believe will find applications in other problems. We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are k-admissible regions (pseudodisks are 2-admissible), and the capacities are bounded. Our result settles a conjecture of Har-Peled (see Conclusion of [Har-Peled, SoCG 2014]) in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane. Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity, extending one of the results of Ene et al. [Ene/Har-Peled/Raichel, SoCG 2012].
Cite as

Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and Covering with Non-Piercing Regions. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{govindarajan_et_al:LIPIcs.ESA.2016.47,
  author =	{Govindarajan, Sathish and Raman, Rajiv and Ray, Saurabh and Basu Roy, Aniket},
  title =	{{Packing and Covering with Non-Piercing Regions}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{47:1--47:17},
  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.47},
  URN =		{urn:nbn:de:0030-drops-63591},
  doi =		{10.4230/LIPIcs.ESA.2016.47},
  annote =	{Keywords: Local Search, Set Cover, Dominating Set, Capacitated Packing, Approximation algorithms}
}
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