Halfspace range search: An algorithmic application of k-sets
Given a fixed set \(S_ n\) of n points in Euclidean space \(E^ 3\) and a query plane \(\pi\), the halfspace range search problem asks for the retrieval of all points of \(S_ n\) on a chosen side of \(\pi\). The authors prove as main results: (1) the total number of j-sets of \(S_ n\) \((=subsets\) of \(S_ n\) of size j which can be separated from the rest of \(S_ n\) by a plane), \(j=1,...,k\), is \(O(nk^ 5)\); (2) using O(n(log n)\({}^ 8(\log \log n)^ 4)\) storage it is possible to solve the above half space range search problem in \(O(k+\log n)\) time, where k is the number of points to be reported.
- A note on Euclidean near neighbor searching in the plane
- Constructing Arrangements of Lines and Hyperplanes with Applications
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3407703 (Why is no real title available?)
- New upper bounds for neighbor searching
- On k-Hulls and Related Problems
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- Edge-skeletons in arrangements with applications
- Line arrangements and range search
- On \(k\)-sets in arrangements of curves and surfaces
- An upper bound on the number of planar K-sets
- Reporting points in halfspaces
- Efficient partition trees
- Cutting dense point sets in half
- Efficient searching with linear constraints
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Dynamic half-space range reporting and its applications
- On k-d Range Search with Patricia Tries
- Tight lower bounds for halfspace range searching
- scientific article; zbMATH DE number 1554935 (Why is no real title available?)
- Simplex Range Searching and Its Variants: A Review
- Robust shape fitting via peeling and grating coresets
- On bounded leg shortest paths problems
- On levels in arrangements and Voronoi diagrams
- Efficient algorithms for maximum regression depth
This page was built for publication: Halfspace range search: An algorithmic application of k-sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077166)
