Abstract
We propose a new query application for the well-known Trapezoidal Search DAG (TSD) of a set of n line segments in the plane, where queries are allowed to be vertical line segments.
We show that a simple Depth-First Search reports the k trapezoids that are intersected by the query segment in \(\mathcal{O}(k+\log n)\) expected time, regardless of the spatial location of the query. This bound is optimal and matches known data structures with \(\mathcal {O}(n)\) size. In the important case of edges from a connected, planar graph, our simplistic approach yields an expected \(\mathcal{O}(n \log ^*\!n)\) construction time, which improves on the construction time of known structures for vertical segment-queries. Also for connected input, a simple extension allows the TSD approach to directly answer axis-aligned window-queries in \(\mathcal{O}(k + \log n)\) expected time, where k is the result size.
See https://arxiv.org/abs/2111.07024 for the full version of this paper.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
I.e. the number of times the \(\log \)-function must be applied to obtain a result \(\le 1\).
- 2.
Our TSD construction in Sect. 2 uses one node of arity four per trapezoid in \(\mathcal T\).
References
Bentley, J.L.: Solutions to Klee’s rectangle problem. Department of Computer Science, Carnegie-Mellon University (1977, unpublished manuscript)
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)
Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., Wein, R.: Arrangements on parametric surfaces I: general framework and infrastructure. Math. Comput. Sci. 4(1), 45–66 (2010)
de Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M.H.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008)
Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. ACM Trans. Algorithms 9(3), 22:1–22:22 (2013)
Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703–724 (1986)
Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discret. Comput. Geom. 4, 387–421 (1989)
Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. In: Proceedings of ACM STOC, pp. 109–121. Association for Computing Machinery, New York (1986)
Edelsbrunner, H.: Dynamic data structures for orthogonal intersection queries. Technische Universität Graz/Forschungszentrum Graz (1980)
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Yormark, B. (ed.) Proceedings of ACM SIGMOD, pp. 47–57. ACM Press (1984)
Hemmer, M., Kleinbort, M., Halperin, D.: Improved implementation of point location in general two-dimensional subdivisions. In: Proceedings of ESA, pp. 611–623 (2012)
McCreight, E.M.: Priority search trees. SIAM J. Comput. 14(2), 257–276 (1985)
Mulmuley, K.: A fast planar partition algorithm, I. J. Symb. Comput. 10(3/4), 253–280 (1990)
Mulmuley, K.: A fast planar partition algorithm, II. J. ACM 38(1), 74–103 (1991)
Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM 29(7), 669–679 (1986)
Seidel, R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. 1, 51–64 (1991)
Seidel, R.: Teaching computational geometry. In: Proceedings of the 5th Canadian Conference on Computational Geometry, CCCG 1993, p. 272 (1993)
Acknowledgements
The authors want to thank Joachim Gudmundsson for suggesting the BFS query of Corollary 1 and an anonymous reviewer for constructive feedback. This work was supported under the Australian Research Council Discovery Projects funding scheme (project number DP180102870).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Brankovic, M., Seybold, M.P. (2022). Optimal Window Queries on Line Segments Using the Trapezoidal Search DAG. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_46
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)