Optimal window queries on line segments using the trapezoidal search DAG

DOI10.1007/978-3-031-22105-7_46arXiv2111.07024OpenAlexW3213863522MaRDI QIDQ6168974

Martin P. Seybold, Milutin Brankovic

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.07024

zbMATH Keywords

depth-first searchline segmentsoutput-sensitivewindow queriestrapezoidal search DAG

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Arrangements on parametric surfaces. I: General framework and infrastructure
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Making data structures persistent
• Applications of random sampling in computational geometry. II
• A fast planar partition algorithm. I
• Improved Implementation of Point Location in General Two-Dimensional Subdivisions
• Persistent Predecessor Search and Orthogonal Point Location on the Word RAM
• Priority Search Trees
• Filtering Search: A New Approach to Query-Answering
• Multidimensional binary search trees used for associative searching
• A fast planar partition algorithm, II

This page was built for publication: Optimal window queries on line segments using the trapezoidal search DAG