TY - JOUR

T1 - On the sum of squares of cell complexities in hyperplane arrangements

AU - Aronov, Boris

AU - Matoušek, Jiří

AU - Sharir, Micha

N1 - Funding Information:
* Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.

PY - 1994/2

Y1 - 1994/2

N2 - Let H be a collection of n hyperplanes in Rd, d≥2. For each cell c of the arrangement of H let fi(c) denote the number of faces of c of dimension i, and let f(c) = ∑i=0d-1 fi(c). We prove that ∑c f(c)2 = O(ndlog 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 Rd is O(m 1 2n d 2log ( 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 2n d 2).

AB - Let H be a collection of n hyperplanes in Rd, d≥2. For each cell c of the arrangement of H let fi(c) denote the number of faces of c of dimension i, and let f(c) = ∑i=0d-1 fi(c). We prove that ∑c f(c)2 = O(ndlog 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 Rd is O(m 1 2n d 2log ( 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 2n d 2).

UR - http://www.scopus.com/inward/record.url?scp=38149147699&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149147699&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(94)90027-2

DO - 10.1016/0097-3165(94)90027-2

M3 - Article

AN - SCOPUS:38149147699

SN - 0097-3165

VL - 65

SP - 311

EP - 321

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 2

ER -