Let H be a collection of n hyperplanes in ℝd, let A denote the arrangement of H, and let σ be a (d-1)-dimensional algebraic surface of low degree, or the boundary of a convex set in ℝd. The zone of σ in A is the collection of cells of A crossed by σ. We show that the total number of faces bounding the cells of the zone of σ is O(nd-1 log n). More generally, if σ has dimension p, 0≤p<d, this quantity is O(n[(d+p)/2]) for d-p even and O(n[(d+p)/2] log n) for d-p odd. These bounds are tight within a logarithmic factor.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics