Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number

DOI10.1137/0221035zbMath0756.68091OpenAlexW2057537033MaRDI QIDQ4016913

Pankaj K. Agarwal

Publication date: 16 January 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221035

zbMATH Keywords

arrangementsspanning treepoint locationzonefractional cascadingray shootingstabbing number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Other problems of combinatorial convexity (52A37) Discrete mathematics in relation to computer science (68R99)

Related Items (10)

On range searching with semialgebraic sets ⋮ Connecting colored point sets ⋮ Connected component and simple polygon intersection searching ⋮ Optimal partition trees ⋮ Applications of a new space-partitioning technique ⋮ Ray shooting and stone throwing with near-linear storage ⋮ Minimizing the stabbing number of matchings, trees, and triangulations ⋮ Connected component and simple polygon intersection searching ⋮ Dynamic data structures for fat objects and their applications ⋮ An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction

This page was built for publication: Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number