Range searching with efficient hierarchical cuttings
From MaRDI portal
Publication:685179
DOI10.1007/BF02573972zbMath0774.68101OpenAlexW2027387410MaRDI QIDQ685179
Publication date: 30 September 1993
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131268
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
On counting point-hyperplane incidences, An efficient \(k\) nearest neighbors searching algorithm for a query line., Lower bounds for off-line range searching, New variants of perfect non-crossing matchings, Computing minimum-area rectilinear convex hull and \(L\)-shape, Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, FITTING A STEP FUNCTION TO A POINT SET WITH OUTLIERS BASED ON SIMPLICIAL THICKNESS DATA STRUCTURES, Orthogonal queries in segments, Topology and combinatorics of partitions of masses by hyperplanes, COMPUTING CLOSEST POINTS FOR SEGMENTS, Almost optimal set covers in finite VC-dimension, Vertical decompositions for triangles in 3-space, Equipartition of mass distributions by hyperplanes, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, Computing depth orders for fat objects and related problems, Algorithms for generalized halfspace range searching and other intersection searching problems, The exact fitting problem in higher dimensions, Connected component and simple polygon intersection searching, Fast algorithms for collision and proximity problems involving moving geometric objects, On fat partitioning, fat covering and the union size of polygons, On Ray Shooting for Triangles in 3-Space and Related Problems, Subquadratic algorithms for algebraic 3SUM, Tree drawings revisited, On reverse shortest paths in geometric proximity graphs, On semialgebraic range reporting, Tight lower bounds for halfspace range searching, Optimal partition trees, Range minima queries with respect to a random permutation, and approximate range counting, Simplex Range Searching and Its Variants: A Review, Approximating the k-Level in Three-Dimensional Plane Arrangements, Trajectory planning for an articulated probe, Constructing minimum-interference networks, Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations, Removing depth-order cycles among triangles: an algorithm generating triangular fragments, Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures, A tight lower bound for computing the diameter of a 3D convex polytope, A greedy clustering algorithm based on interval pattern concepts and the problem of optimal box positioning, Range closest-pair search in higher dimensions, New variants of perfect non-crossing matchings, Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment, Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points, Applications of a new space-partitioning technique, Semi-group range sum revisited: query-space lower bound tightened, On approximate range counting and depth, Linear-space data structures for range mode query in arrays, Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D, Cutting hyperplanes for divide-and-conquer, Equipartitions of measures in $\mathbb{R}^4$, Approximate range searching: The absolute model, Ray shooting and stone throwing with near-linear storage, Efficient image retrieval through vantage objects, Enclosing weighted points with an almost-unit ball, A general approach for cache-oblivious range reporting and approximate range counting, Guarding a terrain by two watchtowers, Lower bounds on the complexity of simplex range reporting on a pointer machine, Unnamed Item, Unnamed Item, The effect of corners on the complexity of approximate range searching, Unnamed Item, New lower bounds for Hopcroft's problem, Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle, On some geometric optimization problems in layered manufacturing, On range searching with semialgebraic sets, A (slightly) faster algorithm for Klee's measure problem, Unnamed Item, Succinct and Implicit Data Structures for Computational Geometry, Dynamic data structures for fat objects and their applications, Extremal point queries with lines and line segments and related problems, Algorithms for generalized halfspace range searching and other intersection searching problems, Approximate range searching, Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems, Reporting intersecting pairs of convex polytopes in two and three dimensions, IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Storing line segments in partition trees
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- An optimal algorithm with unknown time complexity for convex matrix searching
- Cutting hyperplane arrangements
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Implicitly representing arrangements of lines or segments
- Quasi-optimal range searching in spaces of finite VC-dimension
- Spanning trees with low crossing number
- Lower Bounds on the Complexity of Polytope Range Searching
- Space searching for intersecting objects
