×

Orthogonal queries in segments. (English) Zbl 0868.68110

Summary: We consider the orthogonal clipping problem in a set of segments: Given a set of \(n\) segments in \(d\)-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameter \(K\) named the projected-image complexity, which becomes \(\Theta(n^2)\) in the worst case but practically much smaller. If we use \(O(m)\) space, where \(K\log^{4d-7} n\geq m\geq n\log^{4d-7}n\), the query time is \(O((K/m)^{1/2}\log^{\max\{4,4d-5\}}n)\). This is near to an \(\Omega((K/m)^{1/2})\) lower bound.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI

References:

[1] P. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number,Proc. 5th ACM Comput. Geom., 1989, pp. 315–325.
[2] M. Atallah, Some Dynamic Computational Geometry Problems,Comput. Math. Appl. 11 (1985), 1171–1181. · Zbl 0586.68085 · doi:10.1016/0898-1221(85)90105-1
[3] B. Chazelle, Reporting and Counting Segment Intersections,J. Comput. System Sci. 32 (1986), 156–182. · Zbl 0616.68042 · doi:10.1016/0022-0000(86)90025-5
[4] B. Chazelle, Filtering Search: A New Approach to Query-Answering,SIAM J. Comput. 15 (1986), 703–724. · Zbl 0612.68088 · doi:10.1137/0215051
[5] B. Chazelle, A Functional Approach to Data Structures and Its Use in Multidimensional Searching,SIAM J. Comput. 17 (1988), 427–462. · Zbl 0679.68074 · doi:10.1137/0217026
[6] B. Chazelle, Lower Bounds on the Complexity of Polytope Range Searching,J. Amer. Math. Sci. 2 (1989), 637–666. · Zbl 0695.68032 · doi:10.1090/S0894-0347-1989-1001852-0
[7] B. Chazelle, Lower Bounds for Orthogonal Range Searching, I. The Reporting Case,J. Assoc. Comput. Mach. 37 (1990), 200–212. · Zbl 0696.68051
[8] B. Chazelle, M. Sharir, and E. Welzl, Quasi-Optimal Upper Bound for Simplex Range Searching and New Zone Theorems,Algorithmica 8 (1992), 407–429. · Zbl 0788.68141 · doi:10.1007/BF01758854
[9] S. Cheng and R. Janardan, Space-Efficient Ray-Shooting and Intersection Searching,J. Algorithms 13 (1992), 670–692. · Zbl 0767.68089 · doi:10.1016/0196-6774(92)90062-H
[10] D. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348–361. · Zbl 0646.68077 · doi:10.1016/0196-6774(87)90015-0
[11] J. Driscoll, N. Sarnak, D. Slator, and R. Tarjan, Making Data Structure Persistent,J. Comput. System Sci. 38 (1989), 86–124. · Zbl 0667.68026 · doi:10.1016/0022-0000(89)90034-2
[12] M. Edahiro, K. Tanaka, T. Hoshino, and T. Asano, A Bucketing Algorithm for the Orthogonal Segment Intersection Search Problems and Its Practical Efficiency,Algorithmica 4 (1987), 61–76. · Zbl 0664.68064 · doi:10.1007/BF01553879
[13] D. Knuth,Sorting and Searching: The Art of Computer Programming III, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[14] K. Kuse, Private communication.
[15] G. Lueker, A Data Structure for Orthogonal Range Queries,Proc. 19th IEEE FOCS, 1978, pp. 28–34.
[16] J. Matoušek, Efficient Partition Trees,Discrete Comput. Geom. 8 (1992), 315–334. · Zbl 0752.68088 · doi:10.1007/BF02293051
[17] J. Matoušek, Range Searching with Efficient Hierarchical Cuttings,Discrete Comput. Geom. 10 (1993), 157–182. · Zbl 0774.68101 · doi:10.1007/BF02573972
[18] N. Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms,J. Assoc. Comput. Mach. 30 (1983), 852–865. · Zbl 0627.68034
[19] M. H. Overmars,The Design of Dynamic Data Structures, LNCS 156, Springer-Verlag, Berlin, 1983. · Zbl 0545.68009
[20] F. Preparata and M. Shamos,Computational Geometry, an Introduction, 2nd edition, Springer-Verlag, New York, 1988. · Zbl 0575.68059
[21] T. Tokuyama, Orthogonal Range Queries in Segments and Triangles,Proc. 4th ISSAC, LNCS 834, Springer-Verlag, Berlin, 1994, pp. 505–513. · Zbl 0953.68525
[22] D. E. Willard, New Data Structures for Orthogonal Range Queries,SIAM J. Comput. 14 (1985), 232–253. · Zbl 0564.68071 · doi:10.1137/0214019
[23] A. C. Yao, Space-Time Tradeoff for Answering Range Queries,Proc. 14th ACM STOC, 1982, pp. 128–136.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.