On range searching with semialgebraic sets

DOI10.1007/3-540-55808-X_1zbMath1493.68366OpenAlexW1497463354MaRDI QIDQ5096815

Pankaj K. Agarwal, Ji{ří} Matoušek

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55808-x_1

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Semialgebraic sets and related spaces (14P10) Data structures (68P05)

Related Items (4)

On intersection searching problems involving curved objects ⋮ Selection in monotone matrices and computing k th nearest neighbors ⋮ Repetitive hidden-surface-removal for polyhedral scenes ⋮ On the zone of a surface in a hyperplane arrangement

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range searching with efficient hierarchical cuttings
• A deterministic view of random sampling and its use in geometry
• \(\epsilon\)-nets and simplex range queries
• Cutting hyperplane arrangements
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Cutting hyperplanes for divide-and-conquer
• On the zone of a surface in a hyperplane arrangement
• Applications of random sampling in computational geometry. II
• Quasi-optimal range searching in spaces of finite VC-dimension
• Lower Bounds on the Complexity of Polytope Range Searching
• Polygon Retrieval
• Space searching for intersecting objects

This page was built for publication: On range searching with semialgebraic sets