nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles

verfasst von : Timothy M. Chan, Yakov Nekrich, Michiel Smid

Erschienen in: Algorithms and Data Structures

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved.

We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a fat rectangle. Our two-dimensional data structure uses O(n) words and supports queries in \(O(\log \log U +k)\) time, where n is the number of points in the data structure, U is the size of the universe and k is the number of points in the query range. Our three-dimensional data structure needs \(O(n\log ^{\varepsilon }U)\) words of space and answers queries in \(O(\log \log U + k)\) time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses O(n) space and answers stabbing queries in \(O(\log U\log \log U +k)\) time.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Range Closest-Pair Search in Higher Dimensions

Nächstes Kapitel Kernelization of Graph Hamiltonicity: Proper H-Graphs

For simplicity, we ignore the time needed to output points in this section.

Afshani, P.: On dominance reporting in 3D. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 41–51. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87744-8_4CrossRef

Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: Proceedings of 41st Annual Symposium on Foundations of Computer Science, (FOCS 2000), pp. 198–207 (2000)

Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proceedings of 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 346–357 (1999)

Aronov, B., de Berg, M., Gray, C.: Ray shooting and intersection searching amidst fat convex polyhedra in 3-space. Comput. Geom. 41(1–2), 68–76 (2008)MathSciNetCrossRef

Bentley, J.L., Maurer, H.A.: Efficient worst-case data structures for range searching. Acta Inf. 13, 155–168 (1980)MathSciNetCrossRef

Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. ACM Trans. Algorithms 9(3), 22 (2013)MathSciNetCrossRef

Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM. In: Proceedings of 27th ACM Symposium on Computational Geometry (SoCG 2011), pp. 1–10 (2011)

Chan, T.M., Nekrich, Y., Smid, M.: Orthogonal range reporting and rectangle stabbing for fat rectangles. CoRR, abs/1905.02322 (2019)

Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703–724 (1986)MathSciNetCrossRef

10.

Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427–462 (1988)MathSciNetCrossRef

11.

Chazelle, B., Edelsbrunner, H.: Linear space data structures for two types of range search. Discrete Comput. Geom. 2, 113–126 (1987)MathSciNetCrossRef

12.

de Berg, M., Gray, C.: Vertical ray shooting and computing depth orders for fat objects. SIAM J. Comput. 38(1), 257–275 (2008)MathSciNetCrossRef

13.

Efrat, A., Katz, M.J., Nielsen, F., Sharir, M.: Dynamic data structures for fat objects and their applications. Comput. Geom. 15(4), 215–227 (2000)MathSciNetCrossRef

14.

Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of 16th Annual ACM Symposium on Theory of Computing (STOC 1984), pp. 135–143 (1984)

15.

Iacono, J., Langerman, S.: Dynamic point location in fat hyperrectangles with integer coordinates. In: Proceedings of 12th Canadian Conference on Computational Geometry (2000)

16.

Karpinski, M., Nekrich, Y.: Space efficient multi-dimensional range reporting. In: Ngo, H.Q. (ed.) COCOON 2009. LNCS, vol. 5609, pp. 215–224. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02882-3_22CrossRef

17.

Katz, M.J.: 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects. Comput. Geom. 8(6), 299–316 (1997)MathSciNetCrossRef

18.

Kreveld, M.V., Löffler, M.: Range Searching, pp. 1–7. Springer, Heidelberg (2014). https://doi.org/10.1007/978-1-4939-2864-4

19.

Lewenstein, M., Nekrich, Y., Vitter, J.S.: Space-efficient string indexing for wildcard pattern matching. In: Proceedings of 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pp. 506–517 (2014)

20.

McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257–276 (1985)MathSciNetCrossRef

21.

Navarro, G., Nekrich, Y.: Top-k document retrieval in optimal time and linear space. In: Proceedings of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012, pp. 1066–1077 (2012)

22.

Nekrich, Y.: A data structure for multi-dimensional range reporting. In: Proceedings of 23rd ACM Symposium on Computational Geometry (SoCG), pp. 344–353 (2007)

23.

Nekrich, Y.: Space efficient dynamic orthogonal range reporting. Algorithmica 49(2), 94–108 (2007)MathSciNetCrossRef

24.

Nekrich, Y.: Orthogonal Range Searching on Discrete Grids, pp. 1–6. Springer, Boston (2008). https://doi.org/10.1007/978-3-642-27848-8MATH

25.

Rahul, S.: Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in \(\mathbb{R}^3\). In: Proceedings of 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 200–211 (2015)

26.

Vengroff, D.E., Vitter, J.S.: Efficient 3-D range searching in external memory. In: Proceedings of 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 192–201 (1996)

Titel: Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles
verfasst von: Timothy M. Chan
Yakov Nekrich
Michiel Smid
Verlag: Springer International Publishing
Buch: Algorithms and Data Structures
Print ISBN: 978-3-030-24765-2

Electronic ISBN: 978-3-030-24766-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-24766-9_21

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner