LIPIcs.SoCG.2017.55.pdf
- Filesize: 0.64 MB
- 15 pages
Document
Approximate Range Counting Revisited
Author
-
Part of:
Volume:
33rd International Symposium on Computational Geometry (SoCG 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-20
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.SoCG.2017.55
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.
Subject Classification
Keywords
- orthogonal range searching
- rectangle stabbing
- colors
- approximate count
- geometric data structures
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Peyman Afshani and Timothy M. Chan. On approximate range counting and depth. Discrete & Computational Geometry, 42(1):3-21, 2009.
-
Peyman Afshani, Chris H. Hamilton, and Norbert Zeh. A general approach for cache-oblivious range reporting and approximate range counting. Computational Geometry: Theory and Applications, 43(8):700-712, 2010.
-
Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. SIAM Journal of Computing, 38(3):899-921, 2008.
-
Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. Journal of Algorithms, 1(4):301-358, 1980.
-
Timothy M. Chan and Bryan T. Wilkinson. Adaptive and approximate orthogonal range counting. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 241-251, 2013.
-
Bernard Chazelle. Filtering search: A new approach to query-answering. SIAM Journal of Computing, 15(3):703-724, 1986.
-
Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences (JCSS), 47(3):424-436, 1993.
-
Prosenjit Gupta, Ravi Janardan, and Michiel H. M. Smid. Computational geometry: Generalized intersection searching. In Handbook of Data Structures and Applications. 2004.
-
Haim Kaplan, Edgar Ramos, and Micha Sharir. Range minima queries with respect to a random permutation, and approximate range counting. Discrete & Computational Geometry, 45(1):3-33, 2011.
-
Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin. Counting colors in boxes. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 785-794, 2007.
-
Yakov Nekrich. Efficient range searching for categorical and plain data. ACM Transactions on Database Systems (TODS), 39(1):9, 2014.
-
Qingmin Shi and Joseph JáJá. Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines. Information Processing Letters (IPL), 95(3):382-388, 2005.