×

zbMATH — the first resource for mathematics

An (almost) optimal solution for orthogonal point enclosure query in \(\mathbb{R}^3\). (English) Zbl 1434.68135
Summary: The orthogonal point enclosure query (OPEQ) problem is a fundamental problem in the context of data management for modeling user preferences. Formally, preprocess a set \(S\) of \(n\) axis-aligned boxes (possibly overlapping) in \(\mathbb{R}^d\) into a data structure so that the boxes in \(S\) containing a given query point \(q\) can be reported efficiently. In the pointer machine model, optimal solutions for the OPEQ in \(\mathbb{R}^1\) and \(\mathbb{R}^2\) were discovered in the 1980s: linear-space data structures that can answer the query in \(O(\log n + k)\) query time, where \(k\) is the number of boxes reported. However, for the past three decades, an optimal solution in \(\mathbb{R}^3\) has been elusive. In this work, we obtain the first data structure that almost optimally solves the OPEQ in \(\mathbb{R}^3\) in the pointer machine model: an \(O(n \log^\ast n)\)-space data structure with \(O(\log^2n \cdot \log \log n + k)\) query time. Here, \( \log^\ast n\) is the iterated logarithm of \(n\). This almost matches the lower-bound, which states that any data structure that occupies \(O(n)\) space requires \(\Omega (\log^2 n + k)\) time to answer an OPEQ in \(\mathbb{R}^3\). Finally, we also obtain the best known bounds for the OPEQ in higher dimensions \((d \geq 4)\).
MSC:
68P05 Data structures
68P10 Searching and sorting
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W40 Analysis of algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] [1] Afshani P (2008) On dominance reporting in 3D. Proc. 16th Eur. Sympos. Algorithms (Springer, Berlin), 41-51.Google Scholar · Zbl 1158.68363
[2] [2] Afshani P (2013) Improved pointer machine and I/O lower bounds for simplex range reporting and related problems. Internat. J. Comput. Geometry Appl. 23(4-5):233-252.Crossref, Google Scholar · Zbl 1300.68051
[3] [3] Afshani P, Driemel A (2018) On the complexity of range searching among curves. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 898-917.Crossref, Google Scholar · Zbl 1403.68312
[4] [4] Afshani P, Tsakalidis K (2014) Optimal deterministic shallow cuttings for 3D dominance ranges. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1389-1398.Crossref, Google Scholar · Zbl 1422.68232
[5] [5] Afshani P, Arge L, Larsen KD (2010) Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. Kirkpatrick DG, Mitchell JSB, eds. Proc. 26th Annual Sympos. Comput. Geometry (Association for Computing Machinery, New York), 240-246.Crossref, Google Scholar · Zbl 1284.68572
[6] [6] Afshani P, Arge L, Larsen KG (2012) Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. Dey TK, Whitesides S, eds. Proc. 28th Annual Sympos. Comput. Geometry (Association for Computing Machinery, New York), 323-332.Crossref, Google Scholar · Zbl 1293.68278
[7] [7] Afshani P, Sheng C, Tao Y, Wilkinson BT (2014) Concurrent range reporting in two-dimensional space. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 983-994.Crossref, Google Scholar · Zbl 1422.68231
[8] [8] Agarwal PK, Erickson J (1999) Geometric range searching and its relatives. Chazelle B, Goodman JE, Pollack R, eds. Advances in Discrete and Computational Geometry (American Mathematical Society, Providence, RI), 1-56.Google Scholar · Zbl 0916.68031
[9] [9] Agarwal PK, Arge L, Yang J, Yi K (2003) I/O-efficient structures for orthogonal range-max and stabbing-max queries. Di Battista G, Zwick U, eds. Proc. 11th Annual Eur. Sympos. Algorithms (Springer, Basel, Switzerland), 7-18.Crossref, Google Scholar · Zbl 1266.68094
[10] [10] Agarwal PK, Arge L, Kaplan H, Molad E, Tarjan RE, Yi K (2012) An optimal dynamic data structure for stabbing-semigroup queries. SIAM J. Comput. 41(1):104-127.Crossref, Google Scholar · Zbl 1243.68157
[11] [11] Alstrup S, Brodal GS, Rauhe T (2000) New data structures for orthogonal range searching. Proc. 41st Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 198-207.Google Scholar
[12] [12] Arge L, Vitter JS (2003) Optimal external memory interval management. SIAM J. Comput. 32(6):1488-1508.Crossref, Google Scholar · Zbl 1030.68027
[13] [13] Bentley JL (1980) Multidimensional divide-and-conquer. Comm. ACM 23(4):214-229.Crossref, Google Scholar · Zbl 0434.68049
[14] [14] Boroujerdi A, Moret BME (1995) Persistence in computational geometry. Proc. 7th Canadian Conf. Comput. Geometry, 241-246.Google Scholar
[15] [15] Chan TM, Nekrich Y, Rahul S, Tsakalidis K (2018) Orthogonal point location and rectangle stabbing queries in 3-d. Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, eds. Proc. 45th Internat. Colloquium Automata Languages Programming (Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany), 31:1-31:14.Google Scholar
[16] [16] Chazelle B (1986) Filtering search: A new approach to query-answering. SIAM J. Comput. 15(3):703-724.Crossref, Google Scholar · Zbl 0612.68088
[17] [17] Chazelle B (1988) A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3):427-462.Crossref, Google Scholar · Zbl 0679.68074
[18] [18] Chazelle B (1990) Lower bounds for orthogonal range searching: I. The reporting case. J. ACM 37(2):200-212.Crossref, Google Scholar · Zbl 0696.68051
[19] [19] Chazelle B, Rosenberg B (1995) Simplex range reporting on a pointer machine. Comput. Geometry 5(5):237-247.Crossref, Google Scholar · Zbl 0851.68113
[20] [20] de Berg M, Gudmundsson J, Mehrabi AD (2017) Finding pairwise intersections inside a query range. Algorithmica 80(11):3253-3269.Crossref, Google Scholar · Zbl 1410.68367
[21] [21] de Berg M, Cheong O, van Kreveld M, Overmars M (2008) Computational Geometry: Algorithms and Applications, 3rd ed. (Springer-Verlag, Berlin).Crossref, Google Scholar
[22] [22] Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1989) Making data structures persistent. J. Comput. System Sci. 38(1):86-124.Crossref, Google Scholar · Zbl 0667.68026
[23] [23] Edelsbrunner H (1983) A new approach to rectangle intersections, part I. Internat. J. Comput. Math. 13(3-4):209-219.Crossref, Google Scholar · Zbl 0513.68058
[24] [24] Edelsbrunner H, Guibas LJ, Stolfi J (1986) Optimal point location in a monotone subdivision. SIAM J. Comput. 15(2):317-340.Crossref, Google Scholar · Zbl 0602.68102
[25] [25] Feldmann A, Muthukrishnan S (2000) Tradeoffs for packet classification. Proc. IEEE Internat. Conf. Comput. Comm. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1193-1202.Google Scholar
[26] [26] Gupta P, McKeown N (2001) Algorithms for packet classification. IEEE Network 15(2):24-32.Crossref, Google Scholar
[27] [27] Kirkpatrick DG (1983) Optimal search in planar subdivisions. SIAM J. Comput. 12(1):28-35.Crossref, Google Scholar · Zbl 0501.68034
[28] [28] Kung HT, Luccio F, Preparata FP (1975) On finding the maxima of a set of vectors. J. ACM 22(4):469-476.Crossref, Google Scholar · Zbl 0316.68030
[29] [29] Lipton RJ, Tarjan RE (1980) Applications of a planar separator theorem. SIAM J. Comput. 9(3):615-627.Crossref, Google Scholar · Zbl 0456.68077
[30] [30] Makris C, Tsakalidis K (2012) An improved algorithm for static 3D dominance reporting in the pointer machine. Chao K-M, Hsu T, Lee D-T, eds. 23rd Internat. Sympos. Algorithms Comput. (Springer, Basel, Switzerland), 568-577.Google Scholar · Zbl 1260.68420
[31] [31] Mehlhorn K (1984) Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry, Monographs in Theoretical Computer Science, vol. 3 (Springer, Basel, Switzerland).Crossref, Google Scholar
[32] [32] Rahul S (2015) Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in ℝ3. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 200-211.Google Scholar · Zbl 1371.68299
[33] [33] Rahul S (2017) Approximate range counting revisited. Aronov B, Katz MJ, eds. Proc. 33rd Internat. Sympos. Comput. Geometry (Dagstuhl Publishing, Saarbrücken/Wadern, Germany), 55:1-55:15.Google Scholar · Zbl 1432.68102
[34] [34] Rahul S, Tao Y (2016) Efficient top-k indexing via general reductions. Proc. 35th ACM SIGMOD-SIGACT-SIGAI Sympos. Principles Database Systems (Association for Computing Machinery, New York), 277-288.Google Scholar
[35] [35] Sahni S, Kim KS, Lu H (2003) Data structures for one-dimensional packet classification using most-specific-rule matching. Milo T, Tan W-C, eds. Internat. J. Foundations Comput. Sci. 14(3):337-358.Crossref, Google Scholar · Zbl 1101.68497
[36] [36] Sarnak N, Tarjan RE (1986) Planar point location using persistent search trees. Comm. ACM. 29(7):669-679.Crossref, Google Scholar
[37] [37] Snoeyink J (2004) Point location. Goodman JE, O’Rourke J, eds. Handbook of Discrete and Computational Geometry, 2nd ed. (CRC Press, Boca Raton, FL), 767-787.Crossref, Google Scholar
[38] [38] Tarjan RE (1979) A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci. 18(2):110-127.Crossref, · Zbl 0413.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.