Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3

Published Online:10 Oct 2019https://doi.org/10.1287/moor.2019.0994

References

  • [1] Afshani P (2008) On dominance reporting in 3D. Proc. 16th Eur. Sympos. Algorithms (Springer, Berlin), 41–51.Google Scholar
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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] Arge L, Vitter JS (2003) Optimal external memory interval management. SIAM J. Comput. 32(6):1488–1508.Crossref, Google Scholar
  • [13] Bentley JL (1980) Multidimensional divide-and-conquer. Comm. ACM 23(4):214–229.Crossref, Google Scholar
  • [14] Boroujerdi A, Moret BME (1995) Persistence in computational geometry. Proc. 7th Canadian Conf. Comput. Geometry, 241–246.Google Scholar
  • [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] Chazelle B (1986) Filtering search: A new approach to query-answering. SIAM J. Comput. 15(3):703–724.Crossref, Google Scholar
  • [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
  • [18] Chazelle B (1990) Lower bounds for orthogonal range searching: I. The reporting case. J. ACM 37(2):200–212.Crossref, Google Scholar
  • [19] Chazelle B, Rosenberg B (1995) Simplex range reporting on a pointer machine. Comput. Geometry 5(5):237–247.Crossref, Google Scholar
  • [20] de Berg M, Gudmundsson J, Mehrabi AD (2017) Finding pairwise intersections inside a query range. Algorithmica 80(11):3253–3269.Crossref, Google Scholar
  • [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] Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1989) Making data structures persistent. J. Comput. System Sci. 38(1):86–124.Crossref, Google Scholar
  • [23] Edelsbrunner H (1983) A new approach to rectangle intersections, part I. Internat. J. Comput. Math. 13(3–4):209–219.Crossref, Google Scholar
  • [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
  • [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] Gupta P, McKeown N (2001) Algorithms for packet classification. IEEE Network 15(2):24–32.Crossref, Google Scholar
  • [27] Kirkpatrick DG (1983) Optimal search in planar subdivisions. SIAM J. Comput. 12(1):28–35.Crossref, Google Scholar
  • [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
  • [29] Lipton RJ, Tarjan RE (1980) Applications of a planar separator theorem. SIAM J. Comput. 9(3):615–627.Crossref, Google Scholar
  • [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
  • [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] 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
  • [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
  • [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] 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
  • [36] Sarnak N, Tarjan RE (1986) Planar point location using persistent search trees. Comm. ACM. 29(7):669–679.Crossref, Google Scholar
  • [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] Tarjan RE (1979) A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci. 18(2):110–127.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree