Cell complexities in hyperplane arrangements

DOI10.1007/S00454-003-0854-ZMaRDI QIDQ701778zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Micha Sharir

Publication date 16 December 2004

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

Full work available at URL https://doi.org/10.1007/s00454-003-0854-z

zbMATH Keywords

complexityfaceshyperplane arrangements

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Analysis of algorithms and problem complexity (68Q25)

Review text

The complexity of some cells of an hyperplane arrangement in \(R^d\) is the total number of faces of all dimensions of these cells. The authors show that the complexity of \(m\) distinct cells in an arrangement of \(n\) hyperplanes in dimension \(d\geq 4\) is \(O(m^{1/2}n^{d/2}\log^{(\lfloor d/2\rfloor-2)}n)\). They use these new bounds to reobtain a bound for the sum of squares of cell complexities in an arrangement. They also remark that in dimension 4 the bound obtained is tight for different range of values of \(m\).

Recommendations

• On the sum of squares of cell complexities in hyperplane arrangements
• Counting facets and incidences
• On the zone of a surface in a hyperplane arrangement
• The complexity of cells in three-dimensional arrangements
• Cells with many facets in arrangements of hyperplanes

Cited in

(19)

• The complexity of cells in three-dimensional arrangements
• Cells with many facets in arrangements of hyperplanes
• Classification of arrangements by the number of their cells
• On the zone of a surface in a hyperplane arrangement
• Enumerating regular mixed-cell configurations
• On the sum of squares of cell complexities in hyperplane arrangements
• Vertical decomposition of arrangements of hyperplanes in four dimensions
• Rich cells in an arrangement of hyperplanes
• Enumerating colorings, tensions and flows in cell complexes
• scientific article; zbMATH DE number 17391 (Why is no real title available?)
• scientific article; zbMATH DE number 177187 (Why is no real title available?)
• A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search
• Cells in n-fold hyperspaces
• scientific article; zbMATH DE number 1383707 (Why is no real title available?)
• scientific article; zbMATH DE number 1830725 (Why is no real title available?)
• The complexity of many cells in arrangements of planes and related problems
• Sharp bounds for vertical decompositions of linear arrangements in four dimensions
• Semispaces of configurations, cell complexes of arrangements
• Thinning on cell complexes from polygonal tilings

This page was built for publication: Cell complexities in hyperplane arrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q701778)