Dynamic half-space range reporting and its applications
From MaRDI portal
Publication:1891228
DOI10.1007/BF01293483zbMath0827.68037OpenAlexW2032966476MaRDI QIDQ1891228
Pankaj K. Agarwal, Ji{ří} Matoušek
Publication date: 13 December 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01293483
Related Items
Minimum cuts in geometric intersection graphs ⋮ Dynamic coresets ⋮ Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment ⋮ On geometric optimization with few violated constraints ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ Computing the center of uncertain points on cactus graphs ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Facility location and the geometric minimum-diameter spanning tree. ⋮ Iterated snap rounding with bounded drift ⋮ Dynamic geometric data structures via shallow cuttings ⋮ The projection median of a set of points in \({\mathbb{R}}^{d}\) ⋮ REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION ⋮ On polyhedra induced by point sets in space ⋮ Reporting points in halfspaces ⋮ CENTROID TRIANGULATIONS FROM k-SETS ⋮ Efficient partition trees ⋮ Bounded-degree polyhedronization of point sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Dynamic ham-sandwich cuts in the plane ⋮ Two approaches to building time-windowed geometric data structures ⋮ Dynamic data structures for fat objects and their applications ⋮ Polygonal path simplification with angle constraints ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Diameter, width, closest line pair, and parametric searching
- The design of dynamic data structures
- On levels in arrangements and Voronoi diagrams
- Halfspace range search: An algorithmic application of k-sets
- The power of geometric duality
- Maintenance of configurations in the plane
- Euclidean minimum spanning trees and bichromatic closest pairs
- Points and triangles in the plane and halving planes in space
- An upper bound on the number of planar \(K\)-sets
- Maintaining the minimal distance of a point set in polylogarithmic time
- Reporting points in halfspaces
- Applications of a semi-dynamic convex hull algorithm
- Efficient partition trees
- The colored Tverberg's problem and complexes of injective functions
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Counting triangle crossings and halving planes
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Ray Shooting and Parametric Search
- Lower Bounds on the Complexity of Polytope Range Searching
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- A Randomized Algorithm for Closest-Point Queries
- Decomposable searching problems I. Static-to-dynamic transformation
- Point Selections and Weak ε-Nets for Convex Hulls
- Constructing Belts in Two-Dimensional Arrangements with Applications
