Optimal partition trees
From MaRDI portal
Publication:420575
DOI10.1007/S00454-012-9410-ZzbMATH Open1242.68353OpenAlexW4253015087MaRDI QIDQ420575FDOQ420575
Authors: Timothy M. Chan 
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
Recommendations
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- \(\epsilon\)-nets and simplex range queries
- Efficient partition trees
- Applications of random sampling in computational geometry. II
- Almost optimal set covers in finite VC-dimension
- Title not available (Why is that?)
- Title not available (Why is that?)
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
- A deterministic view of random sampling and its use in geometry
- Las Vegas algorithms for linear and integer programming when the dimension is small
- CUTTINGS AND APPLICATIONS
- The multiplicative weights update method: a meta-algorithm and applications
- Title not available (Why is that?)
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Decomposable searching problems I. Static-to-dynamic transformation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal halfspace range reporting in three dimensions
- Efficient searching with linear constraints
- On ray shooting in convex polytopes
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Reporting points in halfspaces
- Applications of a new space-partitioning technique
- 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
- Output-sensitive results on convex hulls, extreme points, and related problems
- Quasi-optimal range searching in spaces of 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
- Polygon Retrieval
- Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
- Linear Optimization Queries
- A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
- Linear programming queries revisited
- Tight lower bounds for halfspace range searching
- Range searching with efficient hierarchical cuttings
Cited In (35)
- Title not available (Why is that?)
- Approximation algorithms for the unit disk cover problem in 2D and 3D
- Multilevel polynomial partitions and simplified range searching
- Partitioning technique for transforming perfect binary trees into single-row networks
- Dynamic geometric data structures via shallow cuttings
- Optimal partition trees
- Title not available (Why is that?)
- Window queries for intersecting objects, maximal points and approximations using coresets
- Range searching with efficient hierarchical cuttings
- On the power of the semi-separated pair decomposition
- Near optimal seperation of tree-like and general resolution
- Efficient partition trees
- Semi-group range sum revisited: query-space lower bound tightened
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Decision trees with optimal joint partitioning
- Title not available (Why is that?)
- Optimal factorizations of families of trees
- Partial enclosure range searching
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Title not available (Why is that?)
- Linear-space data structures for range mode query in arrays
- Efficient independent set approximation in unit disk graphs
- Succinct and Implicit Data Structures for Computational Geometry
- A faster algorithm for computing motorcycle graphs
- Reprint of: Approximating majority depth
- Title not available (Why is that?)
- On reverse shortest paths in geometric proximity graphs
- Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
- Simplex Range Searching and Its Variants: A Review
- Approximating majority depth
- Title not available (Why is that?)
- A note on optimal multiway split trees
- Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
- Range closest-pair search in higher dimensions
- Space-Time Tradeoffs for Emptiness Queries
This page was built for publication: Optimal partition trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q420575)
