Abstract
We present an efficient orthogonal query data structure in a set of segments or triangles in space. The most important feature of our results is that the efficiency of the data structure is highly dependent on the geometric discrete parameters of the input set, as well as its cardinality.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number, Proc. 5th ACM Comput. Geom., (1989), 315–325.
M. Atallah, Some Dynamic Computational Geometry Problems, Computers and Mathematics with Applications, 11 (1985), 1171–1181.
B. Chazelle, Reporting and Counting Segment Intersections, J. Comput. System Sci. 32 (1986) 156–182.
B. Chazelle, Filtering Search: A New Approach to Query-Answering SIAM J. Comput. 15 (1986) 703–724.
B. Chazelle, Lower Bounds on the Complexity of Polytope Range Searching, J. Amer. Math. Sci.,2 (1989) 637–666.
B. Chazelle, Lower Bounds for Orthogonal Range Searching I. The Reporting Case, J. ACM,37 (1990) 200–212.
D. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects, Proc. 25th IEEE FOCS (1984), 387–392.
J. Driscoll, N. Sarnak, D. Slator, and R. Tarjan, Making Data Structure Persistent, Proc. 18th ACM STOC (1986), 109–120.
M. Edahiro, K. Tanaka, T. Hoshiuo, and T. Asano, A Bucketing Algorithm for the Orthogonal Segment Intersection Search Problems and Its Practical Efficiency, Proc. 3rd ACM Comput. Geom. (1987) 258–267.
T. Hirata, J. Matoušek, X. Tan, and T. Tokuyama, Complexity of Projected Images of Convex Subdivisions, Proc. 4th CCCG (1992) 121–126.
K. Kuse, private communication.
G. Lueker, A Data Structure for Orthogonal Range Queries, Proc. 19th IEEE FOCS (1978), 28–34.
K. Mulmuley, A Fast Planar Partition Algorithm, II, Proc. 5th ACM Comput. Geom. (1989), 33–43.
J. Matoušek, Efficient Partition Trees, Proc. 7th ACM Comput. Geom. (1991), 1–9.
J. Matousek, Range Searching with Efficient Hierarchical Cuttings, Proc. 8th ACM Comput. Geom. (1992), 276–285.
F. Preparata and M. Shamos, Computational Geometry, an Introduction, 2nd edition, Springer-Verlag (1988).
A.C. Yao, Space-Time Tradeoff for Answering Range Queries, Proc. 14th ACM STOC (1982), 128–136.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tokuyama, T. (1994). Orthogonal queries in segments and triangles. In: Du, DZ., Zhang, XS. (eds) Algorithms and Computation. ISAAC 1994. Lecture Notes in Computer Science, vol 834. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58325-4_217
Download citation
DOI: https://doi.org/10.1007/3-540-58325-4_217
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58325-7
Online ISBN: 978-3-540-48653-4
eBook Packages: Springer Book Archive