8 Search Results for "De, Minati"

Document
DOI: 10.4230/LIPIcs.ESA.2025.50
Online Hitting Sets for Disks of Bounded Radii

Authors: Minati De, Satyam Singh, and Csaba D. Tóth

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present algorithms for the online minimum hitting set problem in geometric range spaces: Given a set P of n points in the plane and a sequence of geometric objects that arrive one-by-one, we need to maintain a hitting set at all times. For disks of radii in the interval [1,M], we present an O(log M log n)-competitive algorithm. This result generalizes from disks to positive homothets of any convex body in the plane with scaling factors in the interval [1,M]. As a main technical tool, we reduce the problem to the online hitting set problem for a finite subset of integer points and bottomless rectangles. Specifically, for a given N > 1, we present an O(log N)-competitive algorithm for the variant where P is a subset of an N× N section of the integer lattice, and the geometric objects are bottomless rectangles.
Cite as

Minati De, Satyam Singh, and Csaba D. Tóth. Online Hitting Sets for Disks of Bounded Radii. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.ESA.2025.50,
  author =	{De, Minati and Singh, Satyam and T\'{o}th, Csaba D.},
  title =	{{Online Hitting Sets for Disks of Bounded Radii}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{50:1--50:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.50},
  URN =		{urn:nbn:de:0030-drops-245181},
  doi =		{10.4230/LIPIcs.ESA.2025.50},
  annote =	{Keywords: Geometric Hitting Set, Online Algorithm, Homothets, Disks}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.7
Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Authors: Sayan Bandyapadhyay and Eli Mitchell

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study the Discrete Covering with Two Types of Radii problem motivated by its application in wireless networks. In this problem, the goal is to assign either small-range high frequency or large-range low frequency to each access point, maximizing the number of users in high-frequency regions while ensuring that each user is in the range of an access point. Unlike other weighted covering problems, our problem requires satisfying two simultaneous objectives, which calls for novel approaches that leverage the underlying geometry of the problem. In our work, we present two new algorithms: the first is a polynomial-time (2.5 + ε)-approximation, and the second is an exact algorithm for sparse instances, which is fixed-parameter tractable (FPT) in the number of large-radius disks. We also prove that such an FPT algorithm is impossible for general instances lacking sparsity, assuming the Exponential Time Hypothesis. Before our work, the best-known polynomial-time approximation factor was 4 for the problem. Our approximation algorithm results from a fine-grained classification of points that can contribute to the gain of a solution. Based on this classification, we design two sub-algorithms with interdependent guarantees to recover the respective class of points as gain. Our algorithm exploits further properties of Delaunay triangulations to achieve the improved bound. The FPT algorithm is based on branching that utilizes the sparsity of the instances to limit the overall search space.
Cite as

Sayan Bandyapadhyay and Eli Mitchell. Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.WADS.2025.7,
  author =	{Bandyapadhyay, Sayan and Mitchell, Eli},
  title =	{{Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.7},
  URN =		{urn:nbn:de:0030-drops-242386},
  doi =		{10.4230/LIPIcs.WADS.2025.7},
  annote =	{Keywords: Covering, Disks, Approximation, FPT}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.73
Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position

Authors: Anastasiia Tkachenko and Haitao Wang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Given a set P of n points in the plane, its unit-disk graph G(P) is a graph with P as its vertex set such that two points of P are connected by an edge if their (Euclidean) distance is at most 1. We consider several classical problems on G(P) in a special setting when points of P are in convex position. These problems are all NP-hard in the general case. We present efficient algorithms for these problems under the convex position assumption. ● For the problem of finding the smallest dominating set of G(P), we present an O(knlog n) time algorithm, where k is the smallest dominating set size. We also consider the weighted case in which each point of P has a weight and the goal is to find a dominating set in G(P) with minimum total weight; our algorithm runs in O(n³log² n) time. In particular, for a given k, our algorithm can compute in O(kn²log² n) time a minimum weight dominating set of size at most k (if it exists). ● For the discrete k-center problem, which is to find a subset of k points in P (called centers) for a given k, such that the maximum distance between any point in P and its nearest center is minimized. We present an algorithm that solves the problem in O(min{n^{4/3}log n+knlog² n,k² nlog²n}) time, which is O(n²log² n) in the worst case when k = Θ(n). For comparison, the runtime of the current best algorithm for the continuous version of the problem where centers can be anywhere in the plane is O(n³ log n). ● For the problem of finding a maximum independent set in G(P), we give an algorithm of O(n^{7/2}) time and another randomized algorithm of O(n^{37/11}) expected time, which improve the previous best result of O(n⁶log n) time. Our algorithms can be extended to compute a maximum-weight independent set in G(P) with the same time complexities when points of P have weights. - If we are looking for an (unweighted) independent set of size 3, we derive an algorithm of O(nlog n) time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position). - If points of P have weights and are not necessarily in convex position, we present an algorithm that can find a maximum-weight independent set of size 3 in O(n^{5/3+δ}) time for an arbitrarily small constant δ > 0. By slightly modifying the algorithm, a maximum-weight clique of size 3 can also be found within the same time complexity. ● For the dispersion problem, which is to find a subset of k points from P for a given k, such that the minimum pairwise distance of the points in the subset is maximized. We present an algorithm of O(n^{7/2}log n) time and another randomized algorithm of O(n^{37/11}log n) expected time, which improve the previous best result of O(n⁶) time. - If k = 3, we present an algorithm of O(nlog² n) time and another randomized algorithm of O(nlog n) expected time; the previous best algorithm runs in O(n^{4/3}log² n) time (which works for the general case where points of P are not necessarily in convex position).
Cite as

Anastasiia Tkachenko and Haitao Wang. Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tkachenko_et_al:LIPIcs.STACS.2025.73,
  author =	{Tkachenko, Anastasiia and Wang, Haitao},
  title =	{{Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.73},
  URN =		{urn:nbn:de:0030-drops-228982},
  doi =		{10.4230/LIPIcs.STACS.2025.73},
  annote =	{Keywords: Dominating set, k-center, geometric set cover, independent set, clique, vertex cover, unit-disk graphs, convex position, dispersion, maximally separated sets}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.51
Parameterized Geometric Graph Modification with Disk Scaling

Authors: Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph G and an integer k ∈ ℕ as input, the goal is to determine whether we can perform at most k operations on G to transform it into a graph belonging to a specified graph class ℱ. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.
Cite as

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Parameterized Geometric Graph Modification with Disk Scaling. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ITCS.2025.51,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Parameterized Geometric Graph Modification with Disk Scaling}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.51},
  URN =		{urn:nbn:de:0030-drops-226795},
  doi =		{10.4230/LIPIcs.ITCS.2025.51},
  annote =	{Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing}
}
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}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2022
  • 2 2018
  • 1 2012

  • Refine by Author
  • 5 De, Minati
  • 2 Chaplick, Steven
  • 2 Ravsky, Alexander
  • 2 Singh, Satyam
  • 2 Spoerhase, Joachim
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 3 Theory of computation → Packing and covering problems
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 2 Disks
  • 2 approximation scheme
  • 2 balanced separators
  • 2 geometric approximation algorithms
  • 2 local search
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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