Optimal window queries on line segments using the trapezoidal search DAG

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

Authors: Milutin Brankovic, Martin P. Seybold 

Publication date: 10 August 2023

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

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.

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

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

zbMATH Keywords

depth-first searchline segmentsoutput-sensitivewindow queriestrapezoidal search DAG

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)