Point location among hyperplanes and unidirectional ray-shooting

DOI10.1016/0925-7721(94)90009-4zbMath0815.68114OpenAlexW1965491045MaRDI QIDQ1330461

Bernard Chazelle, Joel Friedman

Publication date: 30 June 1995

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(94)90009-4

zbMATH Keywords

point locationquery pointray-shooting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Point location in zones of \(k\)-flats in arrangements ⋮ On ray shooting in convex polytopes ⋮ Dynamic point location in arrangements of hyperplanes ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Cutting hyperplanes for divide-and-conquer ⋮ On the sum of squares of cell complexities in hyperplane arrangements

Cites Work

• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• Optimal randomized parallel algorithms for computational geometry
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• A Randomized Algorithm for Closest-Point Queries