Zone theorem explained

In geometry, the zone theorem is a result that establishes the complexity of the zone of a line in an arrangement of lines.

Definition

A line arrangement, denoted as

A(L) , is a subdivision of the plane, induced by a set of lines L , into cells (2 -dimensional faces), edges (1 -dimensional faces) and vertices (0 -dimensional faces). Given a set of n lines L , the line arrangement A(L) , and a line l (not belonging to L ), the zone of l is the set of faces intersected by l . The complexity of a zone is the total number of edges in its boundary, expressed as a function of n .The zone theorem states that said complexity is O(n) .

History

This result was published for the first time in 1985; Chazelle et al. gave the upper bound of

10 n +2 for the complexity of the zone of a line in an arrangement. In 1991, this bound was improved to \lfloor 9 . 5 n\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 \lfloor 9 . 5 n\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

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

Another generalization is considering arrangements of pseudolines (and pseudohyperplanes in dimension

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

n lines can be done in time O(n ^{2)} , since the insertion of each line takes time O(n) .

References

• .
• .
• .
• .
• .
• .
• .
• .
• .
  • .