Efficient partition trees
From MaRDI portal
Publication:1199132
DOI10.1007/BF02293051zbMath0752.68088OpenAlexW4235042979MaRDI QIDQ1199132
Publication date: 16 January 1993
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131223
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Tighter estimates for \(\epsilon\)-nets for disks ⋮ On range searching with semialgebraic sets ⋮ Crossing families ⋮ On joints in arrangements of lines in space and related problems ⋮ Computing minimum-area rectilinear convex hull and \(L\)-shape ⋮ Efficient algorithms for counting and reporting pairwise intersections between convex polygons ⋮ Covering many or few points with unit disks ⋮ Dynamic half-space range reporting and its applications ⋮ Derandomizing an output-sensitive convex hull algorithm in three dimensions ⋮ 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 ⋮ A survey of mass partitions ⋮ Almost optimal set covers in finite VC-dimension ⋮ 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 ⋮ Improved upper bounds for approximation by zonotopes ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ A deterministic algorithm for the three-dimensional diameter problem ⋮ Fast algorithms for collision and proximity problems involving moving geometric objects ⋮ Subquadratic algorithms for succinct stable matching ⋮ Around the log-rank conjecture ⋮ Indexing moving points ⋮ Semi-algebraic Ramsey numbers ⋮ Optimal partition trees ⋮ Unnamed Item ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Relative \((p,\varepsilon )\)-approximations in geometry ⋮ On bounded leg shortest paths problems ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ Unnamed Item ⋮ OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM ⋮ QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS ⋮ A faster algorithm for computing motorcycle graphs ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures ⋮ Visibility Testing and Counting ⋮ Range closest-pair search in higher dimensions ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ On separating points by lines ⋮ Range searching with efficient hierarchical cuttings ⋮ On ray shooting in convex polytopes ⋮ Tight bounds for connecting sites across barriers ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets ⋮ Equipartitions of measures in $\mathbb{R}^4$ ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses ⋮ Conical equipartitions of mass distributions ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ On grids in point-line arrangements in the plane ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Efficient image retrieval through vantage objects ⋮ Geometric pattern matching for point sets in the plane under similarity transformations ⋮ Efficient \(c\)-oriented range searching with DOP-trees ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Unnamed Item ⋮ Connected component and simple polygon intersection searching ⋮ Unnamed Item ⋮ POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA ⋮ Unnamed Item ⋮ Resolving SINR Queries in a Dynamic Setting ⋮ A practical approximation algorithm for the LMS line estimator ⋮ On Grids in Point-Line Arrangements in the Plane ⋮ Dynamic ham-sandwich cuts in the plane ⋮ Partial Enclosure Range Searching ⋮ A (slightly) faster algorithm for Klee's measure problem ⋮ Unnamed Item ⋮ Finding the \(\Theta \)-guarded region ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Tverberg theorems over discrete sets of points ⋮ Convex subdivisions with low stabbing numbers ⋮ Approximating Minimization Diagrams and Generalized Proximity Search ⋮ 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 ⋮ Efficient searching with linear constraints ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS ⋮ Multilevel polynomial partitions and simplified range searching
Cites Work
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- The design of dynamic data structures
- Partitioning arrangements of lines. II: Applications
- Halfspace range search: An algorithmic application of k-sets
- The power of geometric duality
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Cutting hyperplane arrangements
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Decomposable searching problems
- Quasi-optimal range searching in spaces of finite VC-dimension
- Dynamic half-space range reporting and its applications
- Ray Shooting and Parametric Search
- Lower Bounds on the Complexity of Polytope Range Searching
- Polygon Retrieval
- Dynamic partition trees
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
