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