Zone theorem

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

The zone of a line (red) in an arrangement of lines, consisting of all faces that touch the given line

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 $10n+2$ for the complexity of the zone of a line in an arrangement. In 1991, this bound was improved to $\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 $\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 $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: $$\sum _{i=0}^{d}(-1)^{i}F_{i}\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

• Agarwal, P. K.; Sharir, M. (2000), "Arrangements and their applications" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 49–119.
• Agarwal, P. K.; Sharir, M. (2002), "Pseudo-line arrangements: duality, algorithms, and applications", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco: Society for Industrial and Applied Mathematics, pp. 800–809.
• Aharoni, Y.; Halperin, D.; Hanniel, I.; Har-Peled, S.; Linhart, C. (1999), "On-line zone construction in arrangements of lines in the plane", in Vitter, Jeffrey S.; Zaroliagis, Christos D. (eds.), Algorithm Engineering: 3rd International Workshop, WAE'99, London, UK, July 19–21, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1668, Springer-Verlag, pp. 139–153, CiteSeerX 10.1.1.35.7681, doi:10.1007/3-540-48318-7_13, ISBN 978-3-540-66427-7.
• Bern, M. W.; Eppstein, D.; Plassman, P. E.; Yao, F. F. (1991), "Horizon theorems for lines and polygons" (PDF), in Goodman, J. E.; Pollack, R.; Steiger, W. (eds.), Discrete and Computational Geometry: Papers from the DIMACS Special Year, DIMACS Ser. Discrete Math. and Theoretical Computer Science, vol. 6, Amer. Math. Soc., pp. 45–66, MR 1143288.
• Chazelle, B.; Guibas, L. J.; Lee, D. T. (1985), "The power of geometric duality", BIT Numerical Mathematics, 25 (1): 76–90, doi:10.1007/BF01934990, S2CID 122411548.
• Edelsbrunner, H. (1987), Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, ISBN 978-3-540-13722-1.
• Edelsbrunner, H.; O'Rourke, J.; Seidel, R. (1986), "Constructing arrangements of lines and hyperplanes with applications", SIAM Journal on Computing, 15 (2): 341–363, doi:10.1137/0215024.
• Edelsbrunner, H.; Guibas, L. J. (1989), "Topologically sweeping an arrangement", Journal of Computer and System Sciences, 38 (1): 165–194, doi:10.1016/0022-0000(89)90038-X.
• Edelsbrunner, H.; Guibas, L. J.; Pach, J.; Pollack, R.; Seidel, R.; Sharir, M. (1992), "Arrangements of curves in the plane—topology, combinatorics, and algorithms", Theoretical Computer Science, 92 (2): 319–336, doi:10.1016/0304-3975(92)90319-B.
• Edelsbrunner, H.; Seidel, R.; Sharir, M. (1991), "On the zone theorem for hyperplane arrangements", New Results and New Trends in Computer Science, 555, Graz, Austria: Springer Science & Business Media: 108, doi:10.1016/0304-3975(92)90319-B
• Grünbaum, B. (1972), Arrangements and Spreads, Regional Conference Series in Mathematics, vol. 10, Providence, R.I.: American Mathematical Society.
• Pinchasi, R. (2011), The zone theorem revisited (PDF) (unpublished manuscript)
• Saxena, S. (2021), "Zone theorem for arrangements in dimension three", Information Processing Letters, 172: 106161, arXiv:2006.01428, doi:10.1016/j.ipl.2021.106161, S2CID 219179345