### Abstract

Let H be a collection of n hyperplanes in R^{d}, d≥2. For each cell c of the arrangement of H let f_{i}(c) denote the number of faces of c of dimension i, and let f(c) = ∑_{i=0}^{d-1} f_{i}(c). We prove that ∑_{c} f(c)^{2} = O(n^{d}log^{ d 2-1} n), where the sum extends over all cells of the arrangement. Among other applications, we show that the total number of faces bounding any m distinct cells in an arrangement of n hyperplanes in R^{d} is O(m^{ 1 2}n^{ d 2}log^{ ( d 2-1) 2} n) and provide a lower bound on the maximum possible face count in m distinct cells, which is close to the upper bound, and for many values of m and n is Ω(m^{ 1 2}n^{ d 2}).

Original language | English (US) |
---|---|

Pages (from-to) | 311-321 |

Number of pages | 11 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 65 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1994 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'On the sum of squares of cell complexities in hyperplane arrangements'. Together they form a unique fingerprint.

## Cite this

Aronov, B., Matoušek, J., & Sharir, M. (1994). On the sum of squares of cell complexities in hyperplane arrangements.

*Journal of Combinatorial Theory, Series A*,*65*(2), 311-321. https://doi.org/10.1016/0097-3165(94)90027-2