Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
From MaRDI portal
Publication:2189742
DOI10.1007/s00454-019-00141-7zbMath1442.52020arXiv1712.02913OpenAlexW2995799124MaRDI QIDQ2189742
Esther Ezra, Sariel Har-Peled, Haim Kaplan, Micha Sharir
Publication date: 16 June 2020
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1712.02913
VC-dimensionrandom samplingpoint-locationvertical decompositionbottom-vertex triangulationepsilon-cuttings
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Randomized algorithms (68W20) Combinatorial complexity of geometric structures (52C45)
Related Items
A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Unnamed Item, Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, On 3SUM-hard problems in the decision tree model
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Four results on randomized incremental constructions
- Point location in arrangements of hyperplanes
- Sharp bounds for vertical decompositions of linear arrangements in four dimensions
- A deterministic view of random sampling and its use in geometry
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Vertical decomposition of arrangements of hyperplanes in four dimensions
- A note on point location in arrangements of hyperplanes
- A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
- Shortest path in a polygon using sublinear space
- Learnability and the Vapnik-Chervonenkis dimension
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- A Randomized Algorithm for Closest-Point Queries
- Computing Many Faces in Arrangements of Lines and Segments
- Constructing Planar Cuttings in Theory and Practice
- Linear programming — Randomization and abstract frameworks
- Algorithms in Real Algebraic Geometry: A Survey
- CUTTINGS AND APPLICATIONS
- Near-optimal linear decision trees for k-SUM and related problems
- On the Uniform Convergence of the Frequencies of Occurrence of Events to Their Probabilities
- Lower Bounds for Approximation by Nonlinear Manifolds
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Algorithms in real algebraic geometry
