On the zone of a circle in an arrangement of lines

Abstract

Let $\mathcal{L}$ be a set of $n$ lines in the plane, and let $C$ be a convex curve in the plane, like a circle or a parabola. The "zone" of $C$ in $\mathcal{L}$, denoted $\mathcal{Z}(C,\mathcal{L})$, is defined as the set of all cells in the arrangement $\mathcal{A}(\mathcal{L})$ that are intersected by $C$. Edelsbrunner et al. (1992) showed that the complexity (total number of edges or vertices) of $\mathcal{Z}(C,\mathcal{L})$ is at most $O(n\alpha (n))$, where $\alpha$ is the inverse Ackermann function. They did this by translating the sequence of edges of $\mathcal{Z}(C,\mathcal{L})$ into a sequence $S$ that avoids the subsequence $ababa$. Whether the worst-case complexity of $\mathcal{Z}(C,\mathcal{L})$ is only linear is a longstanding open problem. Since the relaxation of the problem to pseudolines does have a $\Theta (n\alpha (n))$ bound, any proof of $O(n)$ for the case of straight lines must necessarily use geometric arguments. In this paper we present some such geometric arguments. We show that, if $C$ is a circle, then certain configurations of straight-line segments with endpoints on $C$ are impossible. In particular, we show that there exists a Hart-Sharir sequence that cannot appear as a subsequence of $S$. The Hart-Sharir sequences are essentially the only known way to construct $ababa$-free sequences of superlinear length. Hence, if it could be shown that every family of $ababa$-free sequences of superlinear-length eventually contains all Hart-Sharir sequences, it would follow that the complexity of $\mathcal{Z}(C,\mathcal{L})$ is $O(n)$ whenever $C$ is a circle.

More small fixes. 27 pages, 9 figures

References in corpus (2)

• New bounds on the maximum number of edges in $k$-quasi-planar graphs
• Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture