Optimal partition trees
From MaRDI portal
Publication:420575
DOI10.1007/s00454-012-9410-zzbMath1242.68353OpenAlexW4253015087MaRDI QIDQ420575
Publication date: 22 May 2012
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-012-9410-z
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Data structures (68P05)
Related Items
Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Approximating majority depth, Efficient independent set approximation in unit disk graphs, On reverse shortest paths in geometric proximity graphs, Simplex Range Searching and Its Variants: A Review, Reprint of: Approximating majority depth, On the power of the semi-separated pair decomposition, Unnamed Item, A faster algorithm for computing motorcycle graphs, Dynamic geometric data structures via shallow cuttings, Window queries for intersecting objects, maximal points and approximations using coresets, Range closest-pair search in higher dimensions, Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points, Approximation algorithms for the unit disk cover problem in 2D and 3D, Semi-group range sum revisited: query-space lower bound tightened, Linear-space data structures for range mode query in arrays, Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Partial Enclosure Range Searching, Succinct and Implicit Data Structures for Computational Geometry, Multilevel polynomial partitions and simplified range searching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Range searching with efficient hierarchical cuttings
- On ray shooting in convex polytopes
- A deterministic view of random sampling and its use in geometry
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Reporting points in halfspaces
- Applications of a new space-partitioning technique
- 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
- On range searching with semialgebraic sets
- Primal dividing and dual pruning: Output-sensitive construction of four-dimensional polytopes and three-dimensional Voronoi diagrams
- Efficient searching with linear constraints
- Output-sensitive results on convex hulls, extreme points, and related problems
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- Almost optimal set covers in finite VC-dimension
- Simplex range reporting on a pointer machine
- Spanning trees with low crossing number
- Lower Bounds on the Complexity of Polytope Range Searching
- A Randomized Algorithm for Closest-Point Queries
- Partitioning Space for Range Queries
- Decomposable searching problems I. Static-to-dynamic transformation
- Polygon Retrieval
- Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Linear Optimization Queries
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- CUTTINGS AND APPLICATIONS
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- Probability Inequalities for Sums of Bounded Random Variables
- Linear programming queries revisited
- Tight lower bounds for halfspace range searching
