Search Results

Documents authored by Rahul, Saladi

Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.17
Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery Using Drones

Authors: L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra, and Saladi Rahul

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform machine scheduling. For different machine speeds, LPT was first considered by Gonzalez et al. (SIAM J. Comput. 6(1):155–166, 1977). Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take O(mn) time, where m is the number of machines and n is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT. Specifically, the running time is O((n+m)(log²m + log n)). Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope of lines, which has been well studied in the computational geometry community. Our second contribution is to analyze the performance of LPT for the Drones Warehouse Problem (DWP), which is a natural generalization of the uniform machine scheduling problem motivated by drone-based parcel delivery from a warehouse. In this problem, a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it, and returns to the warehouse (where it can also get charged). The speeds and battery lives of the drones could be different, and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of ϕ, where ϕ ≈ 1.62 is the golden ratio.
Cite as

L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra, and Saladi Rahul. Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery Using Drones. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.FSTTCS.2024.17,
  author =	{Chandran, L. Sunil and Gajjala, Rishikesh and Mehra, Shravan and Rahul, Saladi},
  title =	{{Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery Using Drones}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.17},
  URN =		{urn:nbn:de:0030-drops-222060},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.17},
  annote =	{Keywords: Scheduling, Approximation algorithms, Fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.46
Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set

Authors: Arindam Khan, Aditya Lonkar, Saladi Rahul, Aditya Subramanian, and Andreas Wiese

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.FSTTCS.2022.21
A Simple Polynomial Time Algorithm for Max Cut on Laminar Geometric Intersection Graphs

Authors: Utkarsh Joshi, Saladi Rahul, and Josson Joe Thoppil

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2021.22
Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points

Authors: Timothy M. Chan and Saladi Rahul

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2020.64
Active Learning a Convex Body in Low Dimensions

Authors: Sariel Har-Peled, Mitchell Jones, and Saladi Rahul

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.SoCG.2019.61
Searching for the Closest-Pair in a Query Translate

Authors: Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2018.31
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

Authors: Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.SoCG.2018.73
New Bounds for Range Closest-Pair Problems

Authors: Jie Xue, Yuan Li, Saladi Rahul, and Ravi Janardan

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.SoCG.2017.55
Approximate Range Counting Revisited

Authors: Saladi Rahul

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

Abstract
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.
Cite as

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}
}
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