Vertical decomposition of arrangements of hyperplanes in four dimensions

DOI10.1007/BF02570698zbMath0832.68076OpenAlexW2142620572MaRDI QIDQ1895966

Leonidas J. Guibas, Dan Halperin, Micha Sharir, Ji{ří} Matoušek

Publication date: 13 August 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131394

zbMATH Keywords

combinatorial complexityvertical decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Related Items (5)

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ On overlays and minimization diagrams ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces

Cites Work

• A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\)
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• On the sum of squares of cell complexities in hyperplane arrangements
• A Randomized Algorithm for Closest-Point Queries

This page was built for publication: Vertical decomposition of arrangements of hyperplanes in four dimensions