Reporting points in halfspaces
From MaRDI portal
Publication:1196295
DOI10.1016/0925-7721(92)90006-EzbMath0772.68105MaRDI QIDQ1196295
Publication date: 16 December 1992
Published in: Computational Geometry (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (58)
On range searching with semialgebraic sets ⋮ On lines missing polyhedral sets in 3-space ⋮ Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max ⋮ Dynamic half-space range reporting and its applications ⋮ Topology B-trees and their applications ⋮ Algorithms for polytope covering and approximation ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ Almost optimal set covers in finite VC-dimension ⋮ Kinetic sorting and kinetic convex hulls ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ On nearest-neighbor graphs ⋮ Nearest-neighbor searching under uncertainty. I ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ Geometric pattern matching in d-dimensional space ⋮ Optimal partition trees ⋮ Approximate Polytope Membership Queries ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ On Dominance Reporting in 3D ⋮ Dynamic geometric data structures via shallow cuttings ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Range closest-pair search in higher dimensions ⋮ On ray shooting in convex polytopes ⋮ On approximate range counting and depth ⋮ Optimal deterministic shallow cuttings for 3-d dominance ranges ⋮ \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Approximate range searching: The absolute model ⋮ Ray shooting and stone throwing with near-linear storage ⋮ Unnamed Item ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A general approach for cache-oblivious range reporting and approximate range counting ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Two proofs for shallow packings ⋮ Computing coverage kernels under restricted settings ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Unnamed Item ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Unnamed Item ⋮ Smallest k-enclosing rectangle revisited ⋮ Dynamic ham-sandwich cuts in the plane ⋮ Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ Extremal point queries with lines and line segments and related problems ⋮ Efficient searching with linear constraints ⋮ Unnamed Item ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces
Cites Work
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Halfspace range search: An algorithmic application of k-sets
- The power of geometric duality
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- Quasi-optimal range searching in spaces of finite VC-dimension
- Dynamic half-space range reporting and its applications
- Lower Bounds on the Complexity of Polytope Range Searching
- Filtering Search: A New Approach to Query-Answering
- Polygon Retrieval
- Lower bounds on the complexity of simplex range reporting on a pointer machine
This page was built for publication: Reporting points in halfspaces