Halfspace range search: An algorithmic application of k-sets

DOI10.1007/BF02187685zbMath0594.68055OpenAlexW1996570135MaRDI QIDQ1077166

Bernard Chazelle, Franco P. Preparata

Publication date: 1986

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/130983

Mathematics Subject Classification ID

Searching and sorting (68P10) Other problems of combinatorial convexity (52A37) Information storage and retrieval of data (68P20)

Related Items

Edge-skeletons in arrangements with applications ⋮ Dynamic half-space range reporting and its applications ⋮ Cutting dense point sets in half ⋮ Line arrangements and range search ⋮ On bounded leg shortest paths problems ⋮ Simplex Range Searching and Its Variants: A Review ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Efficient algorithms for maximum regression depth ⋮ An upper bound on the number of planar \(K\)-sets ⋮ Reporting points in halfspaces ⋮ Efficient partition trees ⋮ Robust shape fitting via peeling and grating coresets ⋮ New applications of random sampling in computational geometry ⋮ Applications of random sampling in computational geometry. II ⋮ Efficient searching with linear constraints ⋮ On levels in arrangements and Voronoi diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• A note on Euclidean near neighbor searching in the plane
• New upper bounds for neighbor searching
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On k-Hulls and Related Problems
• On k-Nearest Neighbor Voronoi Diagrams in the Plane