Zone theorem

History

This result was published for the first time in 1985; Chazelle et al. gave the upper bound of ${\displaystyle 10n+2}$ for the complexity of the zone of a line in an arrangement. In 1991, this bound was improved to ${\displaystyle \lfloor 9.5n\rfloor -1}$, and it was also shown that this is the best possible upper bound up to a small additive factor. Then, in 2011, Rom Pinchasi proved that the complexity of the zone of a line in an arrangement is at most ${\displaystyle \lfloor 9.5n\rfloor -3}$, and this is a tight bound.

Some paradigms used in the different proofs of the theorem are induction, sweep technique, tree construction, and Davenport-Schinzel sequences.

Generalizations

Although the most popular version is for arrangements of lines in the plane, there exist some generalizations of the zone theorem. For instance, in dimension ${\displaystyle d}$, considering arrangements of hyperplanes, the complexity of the zone of a hyperplane ${\displaystyle h}$ is the number of facets (${\displaystyle d-1}$ - dimensional faces) bounding the set of cells (${\displaystyle d}$-dimensional faces) intersected by ${\displaystyle h}$. Analogously, the ${\displaystyle d}$-dimensional zone theorem states that the complexity of the zone of a hyperplane is ${\displaystyle O(n^{d-1})}$. There are considerably fewer proofs for the theorem for dimension ${\displaystyle d\ge 3}$. For the ${\displaystyle 3}$-dimensional case, there are proofs based on sweep techniques and for higher dimensions is used Euler’s relation: $${\displaystyle \sum _{i=0}^d(-1{)}^i{F}_i\ge 0.}$$

Another generalization is considering arrangements of pseudolines (and pseudohyperplanes in dimension ${\displaystyle d}$) instead of lines (and hyperplanes). Some proofs for the theorem work well in this case since they do not use the straightness of the lines substantially through their arguments.

Motivation

The primary motivation to study the zone complexity in arrangements arises from looking for efficient algorithms to construct arrangements. A classical algorithm is the incremental construction, which can be roughly described as adding the lines one after the other and storing all faces generated by each in an appropriate data structure (the usual structure for arrangements is the doubly connected edge list (DCEL)). Here, the consequence of the zone theorem is that the entire construction of any arrangement of ${\displaystyle n}$ lines can be done in time ${\displaystyle O(n^2)}$, since the insertion of each line takes time ${\displaystyle O(n)}$.