Optimal window queries on line segments using the trapezoidal search DAG

DOI10.1007/978-3-031-22105-7_46MaRDI QIDQ6168974zbMATH OpenOpenAlexFDO

Authors Milutin Brankovic, Martin P. Seybold

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)

Abstract: We propose new query applications of the well-known Trapezoidal Search DAG (TSD) on a set of $n$ line segments in the plane, where queries are allowed to be {em vertical line segments}. We show that our algorithm reports the $k$ trapezoids that are intersected by the query segment in $calO(k+logn)$ expected time, regardless of the spatial location of the segment set and the query. This improves on the query time and space bound of the well-known Segment Tree based approach, which is to date the theoretical bottleneck for optimal query time. In the case where the set of segments is a connected planar subdivision, this method can easily be extended to report the $k$ segments which intersect an axis aligned query window in $calO(k+logn)$ expected time. Our publicly available implementation handles degeneracies exactly, including segments with overlap and multi-intersections. Experiments on real and synthetic data sets show that the method is practical and provides more reliable query times in comparison to R-trees and the segment tree based data structure.

Recommendations

• Near optimal line segment queries in simple polygons
• scientific article; zbMATH DE number 1869802
• Window queries for problems on intersecting objects and maximal points
• Window queries for intersecting objects, maximal points and approximations using coresets
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• An optimal algorithm for decomposing a window into maximal quadtree blocks
• Searching on a line: a complete characterization of the optimal solution
• Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs
• scientific article; zbMATH DE number 2159654

Cites work

• A fast planar partition algorithm, II
• A fast planar partition algorithm. I
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• Applications of random sampling in computational geometry. II
• Arrangements on parametric surfaces. I: General framework and infrastructure
• Computational geometry. Algorithms and applications.
• Filtering Search: A New Approach to Query-Answering
• Improved implementation of point location in general two-dimensional subdivisions
• Making data structures persistent
• Multidimensional binary search trees used for associative searching
• Persistent predecessor search and orthogonal point location on the word RAM
• Priority Search Trees

Cited in

(1)

• scientific article; zbMATH DE number 1869802 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168974)