Space searching for intersecting objects

DOI10.1016/0196-6774(87)90015-0zbMath0646.68077OpenAlexW2043615835MaRDI QIDQ5903665

David P. Dobkin, Herbert Edelsbrunner

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90015-0

zbMATH Keywords

data structuregeometric complexitygeometric intersectionham-sandwich cutsham- sandwhich tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Efficient ray shooting and hidden surface removal, Orthogonal queries in segments, Algorithms for generalized halfspace range searching and other intersection searching problems, Connected component and simple polygon intersection searching, Storing line segments in partition trees, Intersection queries in sets of disks, The power of parallel projection, On range searching with semialgebraic sets, Algorithms for generalized halfspace range searching and other intersection searching problems, Weak visibility counting in simple polygons, An improved technique for output-sensitive hidden surface removal