The authors show a tight bound on the maximum number of facets bounding \(n^{d-2}\leq m\leq n^ d\) distinct cells in arrangements on \(n\) hyperplanes in \(R^ d\). This yields a tight bound on the number of incidences between \(n\) hyperplanes in \(R^ d\) and \(m\) vertices in their arrangement. The same technique is employed to obtain a tight bound on the number of faces bounding all nonconvex cells in arrangements of triangles in \(R^ 3\). Some open questions are given.
Recommendations
Cites work
- Castles in the air revisited
- Combinatorial complexity bounds for arrangements of curves and spheres
- Extremal problems in discrete geometry
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
- On the maximal number of edges of many faces in an arrangement
- On the sum of squares of cell complexities in hyperplane arrangements
- Partitioning Space for Range Queries
- The complexity of cells in three-dimensional arrangements
- The complexity of many cells in arrangements of planes and related problems
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- Triangles in space or building (and analyzing) castles in the air
Cited in
(18)- The complexity of cells in three-dimensional arrangements
- Cells with many facets in arrangements of hyperplanes
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- On the sum of squares of cell complexities in hyperplane arrangements
- Castles in the air revisited
- Many-face complexity in incremental convex arrangements
- Polytopes in arrangements
- A new technique for analyzing substructures in arrangements of piecewise linear surfaces
- Robot motion planning and the single cell problem in arrangements
- On counting point-hyperplane incidences
- Counting faces in the extended Shi arrangement
- Nondegenerate spheres in four dimensions
- On a Question of Bourgain about Geometric Incidences
- On the number of regions in an m-dimensional space cut by n hyperplanes
- A bichromatic incidence bound and an application
- Covering points by hyperplanes and related problems
- Cell complexities in hyperplane arrangements
- Two theorems on point-flat incidences
This page was built for publication: Counting facets and incidences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1189286)
