Document

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

Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), m sets (resp. n points) are given and n points (resp. m sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution.
For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight O(log n)-competitive algorithm. In the same setting for hitting set, we provide a tight O(log N)-competitive algorithm, assuming that all points have integral coordinates in [0,N)². No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems).
For both dynamic set cover and hitting set with d-dimensional hyperrectangles, we obtain (log m)^O(d)-approximation algorithms with (log m)^O(d) worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an extended quad-tree approach and a frequency reduction technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.

Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese. Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.SoCG.2023.46, author = {Khan, Arindam and Lonkar, Aditya and Rahul, Saladi and Subramanian, Aditya and Wiese, Andreas}, title = {{Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {46:1--46:17}, 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.46}, URN = {urn:nbn:de:0030-drops-178967}, doi = {10.4230/LIPIcs.SoCG.2023.46}, annote = {Keywords: Geometric Set Cover, Hitting Set, Rectangles, Squares, Hyperrectangles, Online Algorithms, Dynamic Data Structures} }

Document

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

In a geometric intersection graph, given a collection of n geometric objects as input, each object corresponds to a vertex and there is an edge between two vertices if and only if the corresponding objects intersect. In this work, we present a somewhat surprising result: a polynomial time algorithm for max cut on laminar geometric intersection graphs. In a laminar geometric intersection graph, if two objects intersect, then one of them will completely lie inside the other. To the best of our knowledge, for max cut this is the first class of (non-trivial) geometric intersection graphs with an exact solution in polynomial time. Our algorithm uses a simple greedy strategy. However, proving its correctness requires non-trivial ideas.
Next, we design almost-linear time algorithms (in terms of n) for laminar axis-aligned boxes by combining the properties of laminar objects with vertical ray shooting data structures. Note that the edge-set of the graph is not explicitly given as input; only the n geometric objects are given as input.

Utkarsh Joshi, Saladi Rahul, and Josson Joe Thoppil. A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs. 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. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{joshi_et_al:LIPIcs.FSTTCS.2022.21, author = {Joshi, Utkarsh and Rahul, Saladi and Thoppil, Josson Joe}, title = {{A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {21:1--21:12}, 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.21}, URN = {urn:nbn:de:0030-drops-174139}, doi = {10.4230/LIPIcs.FSTTCS.2022.21}, annote = {Keywords: Geometric intersection graphs, Max cut, Vertical ray shooting} }

Document

**Published in:** LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

In this paper, we present simple randomized multi-pass streaming algorithms for fundamental computational geometry problems of finding the skyline (maximal) points and the extreme points of the convex hull. For the skyline problem, one of our algorithm occupies O(h) space and performs O(log n) passes, where h is the number of skyline points. This improves the space bound of the currently best known result by Das Sarma, Lall, Nanongkai, and Xu [VLDB'09] by a logarithmic factor. For the extreme points problem, we present the first non-trivial result for any constant dimension greater than two: an O(h log^{O(1)}n) space and O(log^dn) pass algorithm, where h is the number of extreme points. Finally, we argue why randomization seems unavoidable for these problems, by proving lower bounds on the performance of deterministic algorithms for a related problem of finding maximal elements in a poset.

Timothy M. Chan and Saladi Rahul. Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2021.22, author = {Chan, Timothy M. and Rahul, Saladi}, title = {{Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.22}, URN = {urn:nbn:de:0030-drops-136674}, doi = {10.4230/LIPIcs.STACS.2021.22}, annote = {Keywords: multi-pass streaming algorithms, skyline, convex hull, extreme points, randomized algorithms} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Consider a set P ⊆ ℝ^d of n points, and a convex body C provided via a separation oracle. The task at hand is to decide for each point of P if it is in C using the fewest number of oracle queries. We show that one can solve this problem in two and three dimensions using O(⬡_P log n) queries, where ⬡_P is the largest subset of points of P in convex position. In 2D, we provide an algorithm which efficiently generates these adaptive queries.
Furthermore, we show that in two dimensions one can solve this problem using O(⊚(P,C) log² n) oracle queries, where ⊚(P,C) is a lower bound on the minimum number of queries that any algorithm for this specific instance requires. Finally, we consider other variations on the problem, such as using the fewest number of queries to decide if C contains all points of P.
As an application of the above, we show that the discrete geometric median of a point set P in ℝ² can be computed in O(n log² n (log n log log n + ⬡(P))) expected time.

Sariel Har-Peled, Mitchell Jones, and Saladi Rahul. Active Learning a Convex Body in Low Dimensions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.ICALP.2020.64, author = {Har-Peled, Sariel and Jones, Mitchell and Rahul, Saladi}, title = {{Active Learning a Convex Body in Low Dimensions}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {64:1--64:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.64}, URN = {urn:nbn:de:0030-drops-124711}, doi = {10.4230/LIPIcs.ICALP.2020.64}, annote = {Keywords: Approximation algorithms, computational geometry, separation oracles, active learning} }

Document

**Published in:** LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

We consider a range-search variant of the closest-pair problem. Let Gamma be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.

Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. Searching for the Closest-Pair in a Query Translate. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{xue_et_al:LIPIcs.SoCG.2019.61, author = {Xue, Jie and Li, Yuan and Rahul, Saladi and Janardan, Ravi}, title = {{Searching for the Closest-Pair in a Query Translate}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {61:1--61:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.61}, URN = {urn:nbn:de:0030-drops-104659}, doi = {10.4230/LIPIcs.SoCG.2019.61}, annote = {Keywords: Closest pair, Range search, Geometric data structures, Translation query} }

Document

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

In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing.
- Orthogonal point location. We give the first linear-space data structure that supports 3-d point location queries on n disjoint axis-aligned boxes with optimal O(log n) query time in the (arithmetic) pointer machine model. This improves the previous O(log^{3/2} n) bound of Rahul [SODA 2015]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time.
- Rectangle stabbing. We give the first linear-space data structure that supports 3-d 4-sided and 5-sided rectangle stabbing queries in optimal O(log_wn+k) time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-k rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing.
For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant of Alstrup, Brodal, and Rauhe's grid-based recursive technique (FOCS 2000), combined with a number of new ideas.

Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. Orthogonal Point Location and Rectangle Stabbing Queries in 3-d. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.ICALP.2018.31, author = {Chan, Timothy M. and Nekrich, Yakov and Rahul, Saladi and Tsakalidis, Konstantinos}, title = {{Orthogonal Point Location and Rectangle Stabbing Queries in 3-d}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {31:1--31:14}, 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.31}, URN = {urn:nbn:de:0030-drops-90352}, doi = {10.4230/LIPIcs.ICALP.2018.31}, annote = {Keywords: geometric data structures, orthogonal point location, rectangle stabbing, pointer machines, I/O model, word RAM model} }

Document

**Published in:** LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Given a dataset S of points in R^2, the range closest-pair (RCP) problem aims to preprocess S into a data structure such that when a query range X is specified, the closest-pair in S cap X can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.

Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan. New Bounds for Range Closest-Pair Problems. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{xue_et_al:LIPIcs.SoCG.2018.73, author = {Xue, Jie and Li, Yuan and Rahul, Saladi and Janardan, Ravi}, title = {{New Bounds for Range Closest-Pair Problems}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {73:1--73:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.73}, URN = {urn:nbn:de:0030-drops-87865}, doi = {10.4230/LIPIcs.SoCG.2018.73}, annote = {Keywords: Closest-pair, Range search, Candidate pairs, Average-case analysis} }

Document

**Published in:** LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

We study range-searching for colored objects, where one has to count (approximately) the number of colors present in a query range. The problems studied mostly involve orthogonal range-searching in two and three dimensions, and the dual setting of rectangle stabbing by points. We present optimal and near-optimal solutions for these problems. Most of the results are obtained via reductions to the approximate uncolored version, and improved data-structures for them. An additional contribution of this work is the introduction of nested shallow cuttings.

Saladi Rahul. Approximate Range Counting Revisited. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{rahul:LIPIcs.SoCG.2017.55, author = {Rahul, Saladi}, title = {{Approximate Range Counting Revisited}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {55:1--55:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.55}, URN = {urn:nbn:de:0030-drops-72354}, doi = {10.4230/LIPIcs.SoCG.2017.55}, annote = {Keywords: orthogonal range searching, rectangle stabbing, colors, approximate count, geometric data structures} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail