Search Results

Documents authored by De, Minati

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.17
Online Piercing of Geometric Objects

Authors: Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We consider the online version of the piercing set problem where geometric objects arrive one by one. The online algorithm must maintain a piercing set for the arrived objects by making irrevocable decisions. First, we show that any deterministic online algorithm that solves this problem has a competitive ratio of at least Ω(n), which even holds when the objects are one-dimensional intervals. On the other hand, piercing unit objects is equivalent to the unit covering problem which is well-studied in the online model. Due to this, all the results related to the online unit covering problem are preserved for the online unit piercing problem when the objects are translated from each other. Surprisingly, no upper bound was known for the unit covering problem when unit objects are anything other than balls and hypercubes. In this paper, we introduce the notion of α-aspect and α-aspect_∞ objects. We give an upper bound of competitive ratio for α-aspect and α-aspect_∞ objects in ℝ³ and ℝ^d, respectively, with a scaling factor in the range [1,k]. We also propose a lower bound of the competitive ratio for bounded scaled objects like α-aspect objects in ℝ², axis-aligned hypercubes in ℝ^d, and balls in ℝ² and ℝ³. For piercing α-aspect_∞ objects in ℝ^d, we show that a simple deterministic algorithm achieves a competitive ratio of at most (2/α)^d((1+α)^d-1) (⌈log_(1+α)(2k/α)⌉)+1. This result is very general in nature. One can obtain upper bounds for specific objects by specifying the value of α. By putting the value of k = 1 to the above result, we get an upper bound of the competitive ratio for the unit covering problem for various types of objects.
Cite as

Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online Piercing of Geometric Objects. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.FSTTCS.2022.17,
  author =	{De, Minati and Jain, Saksham and Kallepalli, Sarat Varma and Singh, Satyam},
  title =	{{Online Piercing of Geometric Objects}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.17},
  URN =		{urn:nbn:de:0030-drops-174090},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.17},
  annote =	{Keywords: piercing set problem, online algorithm, competitive ratio, unit covering problem, geometric objects}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.17
Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

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

Abstract
In their seminal work, Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010] showed that a wide class of geometric set cover (SC) problems admit a PTAS via local search - this is one of the most general approaches known for such problems. Their result applies if a naturally defined "exchange graph" for two feasible solutions is planar and is based on subdividing this graph via a planar separator theorem due to Frederickson [Greg N. Frederickson, 1987]. Obtaining similar results for the related maximum coverage problem (MC) seems non-trivial due to the hard cardinality constraint. In fact, while Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] have shown (via a different analysis) that local search yields a PTAS for two-dimensional real halfspaces, they only conjectured that the same holds true for dimension three. Interestingly, at this point it was already known that local search provides a PTAS for the corresponding set cover case and this followed directly from the approach of Mustafa and Ray. In this work we provide a way to address the above-mentioned issue. First, we propose a color-balanced version of the planar separator theorem. The resulting subdivision approximates locally in each part the global distribution of the colors. Second, we show how this roughly balanced subdivision can be employed in a more careful analysis to strictly obey the hard cardinality constraint. More specifically, we obtain a PTAS for any "planarizable" instance of MC and thus essentially for all cases where the corresponding SC instance can be tackled via the approach of Mustafa and Ray. As a corollary, we confirm the conjecture of Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding real halfspaces in dimension three. We feel that our ideas could also be helpful in other geometric settings involving a cardinality constraint.
Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ESA.2018.17,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{17:1--17:15},
  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.17},
  URN =		{urn:nbn:de:0030-drops-94809},
  doi =		{10.4230/LIPIcs.ESA.2018.17},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.107
Brief Announcement: Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

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

Abstract
In this announcement, we show that the classical Maximum Coverage problem (MC) admits a PTAS via local search in essentially all cases where the corresponding instances of Set Cover (SC) admit a PTAS via the local search approach by Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010]. As a corollary, we answer an open question by Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding half-spaces in R^3 thereby settling the existence of PTASs for essentially all natural cases of geometric MC problems. As an intermediate result, we show a color-balanced version of the classical planar subdivision theorem by Frederickson [Greg N. Frederickson, 1987]. We believe that some of our ideas may be useful for analyzing local search in other settings involving a hard cardinality constraint.
Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Brief Announcement: Approximation Schemes for Geometric Coverage Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 107:1-107:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ICALP.2018.107,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Brief Announcement: Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{107:1--107:4},
  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.107},
  URN =		{urn:nbn:de:0030-drops-91113},
  doi =		{10.4230/LIPIcs.ICALP.2018.107},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.510
Minimum Enclosing Circle with Few Extra Variables

Authors: Minati De, Subhas C. Nandy, and Sasanka Roy

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
Asano et al. [JoCG 2011] proposed an open problem of computing the minimum enclosing circle of a set of n points in R^2 given in a read-only array in sub-quadratic time. We show that Megiddo's prune and search algorithm for computing the minimum radius circle enclosing the given points can be tailored to work in a read-only environment in O(n^{1+epsilon}) time using O(log n) extra space, where epsilon is a positive constant less than 1. As a warm-up, we first solve the same problem in an in-place setup in linear time with O(1) extra space.
Cite as

Minati De, Subhas C. Nandy, and Sasanka Roy. Minimum Enclosing Circle with Few Extra Variables. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 510-521, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.FSTTCS.2012.510,
  author =	{De, Minati and Nandy, Subhas C. and Roy, Sasanka},
  title =	{{Minimum Enclosing Circle with Few Extra Variables}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{510--521},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.510},
  URN =		{urn:nbn:de:0030-drops-38855},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.510},
  annote =	{Keywords: Minimum enclosing circle, space-efficient algorithm, prune-and-search}
}
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