On the sum of squares of cell complexities in hyperplane arrangements
type: Item
instance of: scholarly article
title: On the sum of squares of cell complexities in hyperplane arrangements
zbMATH Open document ID: 0799.52009
DOI: 10.1016/0097-3165(94)90027-2
published in: Journal of Combinatorial Theory. Series A
publication date: 1994-06-06T00:00:00Z
review text: For an arrangement \(A\) of \(n\) hyperplanes in \(\mathbb{R}^ d\) \((d \geq 2)\), let \(f_ i (c)\) denote the number of \(i\)-dimensional faces of a cell \(c\) of \(A\), and let \(f(c) = \sum^{d-1}_{i = 0} f_ i(c)\) be the complexity of the cell \(c\). The authors prove that \[ \sum_ c f(c)^ 2 = O \Bigl( n^ d \log^{\lfloor {d \over 2} \rfloor - 1}n \Bigr), \tag{*} \] where the sum extends over all cells of \(A\), and the constant of proportionality depends on \(d\). Moreover, it is shown that the total number of faces, bounding any \(m\) distinct cells of \(A\), is \(O(m^{{1 \over 2}} n^{{1 \over 2}} \log^{(\lfloor {1 \over 2} \rfloor - 1) \cdot {1 \over 2}} n)\), and several further applications regarding face count are added. Finally, in view of \((*)\) the authors conjecture that the correct bound is \(\Theta (n^ d)\).
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52C35
zbMATH DE Number: 554404
zbMATH Keywords: arrangement of hyperplanes
zbMATH Keywords: cell complexity
zbMATH Keywords: zones of arrangements
zbMATH Keywords: face count
Wikidata QID: Q56442898
author: Boris Aronov
author: Jiří Matoušek
author: Micha Sharir
MaRDI profile type: Publication
full work available at URL: 0097-3165(94)90027-2
OpenAlex ID: W2043060962
cites work: Counting facets and incidences
cites work: On the zone of a surface in a hyperplane arrangement
cites work: Castles in the air revisited
cites work: Point location among hyperplanes and unidirectional ray-shooting
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: Applications of random sampling in computational geometry. II
cites work: Q3772828
cites work: The complexity of many cells in arrangements of planes and related problems
cites work: On the Zone Theorem for Hyperplane Arrangements
cites work: On vertical ray shooting in arrangements
description: scientific article; zbMATH DE number 554404