On the zone of a circle in an arrangement of lines

Let 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 L, denoted Z(C,L), is defined as the set of all faces in the arrangement A(L) that are intersected by C. Edelsbrunner et al. (1992) showed that the complexity (total number of edges or vertices) of Z(C,L) is at most O(nα(n)), where α is the inverse Ackermann function, by translating the sequence of edges of Z(C,L) into a sequence S that avoids the subsequence ababa. Whether the worst-case complexity of Z(C,L) is only linear is a longstanding open problem.In this paper we provide evidence that, if C is a circle or a parabola, then the zone of C has at most linear complexity: We show that a certain configuration of segments with endpoints on C is impossible. As a consequence, the Hart–Sharir sequences, which are essentially the only known way to construct ababa-free sequences of superlinear length, cannot occur in S.Hence, if it could be shown that every family of superlinear-length, ababa-free sequences must eventually contain all Hart–Sharir sequences, that would settle the zone problem for a circle/parabola.