A more intuitive proof of the Zone theorem ?

Question

The Zone theorem says that if we stab an arrangement of n lines with another line, the total complexity of its zone, the set of all 0-, 1-, and 2-faces adjacent to it, is O(n). The actual constant is something like 6n at least as stated in various textbooks, and the proof is by induction with a reasonably careful charging argument.

I was asked this question in class, and don't have an answer:

Is there an alternate, more intuitive proof of the Zone theorem ?

Now I realize that many people find induction quite intuitive and would be offended by my implication, and am willing to amend the above to merely "alternate" for them. But is there any such proof ? Or even a proof from the book ?

Answer 1

This is not cleaner, but it is a good preparation for more advanced stuff, and it is a good example of abstraction...

One can use Davenport-Schinzel sequences argument. Consider the region above your zone line. Every line becomes a ray, and in fact two rays, as we consider the left side and right side as being different. Scan the boundary of this zone from left to right, writing down which rays you encounter. This is a sequence defined over 2n symbols, and the pattern abab is illegal. As such, the length of the sequence is at most 2(2n)-1 = 4n-1. Applying it to the zone below the line, implies a bound of the form 8n.

Now, proving that a sequence of symbols without ...a..b..a..b... as a subsequence of n symbols has length 2n-1 is easy. indeed, consider two consecutive appearances of the same character that are closest to each other in this sequence. Clearly, in between these two characters, each character that appears must be unique. Consider such a character, and observe that if it appears anywhere else in the string, then we will get the forbidden subsequence. As such, this character appears exactly once in the string. Remove it, and remove an extra character if needed if you created two consecutive identical characters. Namely, removing a character from the string shorten it by 2, as such, the maximum length of the string is 2n-1.

Answer 2

I find induction quite intuitive and am offended by your implication. But what charging argument?

Wlog assume the line defining the zone is horizontal (else rotate) and that the lines are in general position (else perturb and make the zone more complicated). Remove one of the other n lines. Classify the edges of the resulting zone as left or right boundaries, depending on whether the zone is to their right or left, respectively. (Some edges are both left and right boundaries, but they're counted twice in the complexity bound.) By the inductive hypothesis, there are at most 3n-3 left boundaries. (The base case n=0 is trivial.) Reinserting the deleted line adds at most 3 left boundaries (one on the line itself, and two from splitting older left boundaries). Thus, the total number of left boundaries is at most 3n. Symmetrically, the number of right boundaries is at most 3n, so the total complexity of the zone is at most 6n.

Answer 3

A proof by a charging argument is posed as an exercise (together with step by step hints) on page 13 of David Mount's computational geometry class handouts: http://www.cs.umd.edu/class/fall2005/cmsc754/Handouts/cmsc754-handouts.pdf