On the zone of a circle in an arrangement of lines

详细信息    查看全文

• 作者：Gabriel Nivasch ^{gabrieln@ariel.ac.il" class="auth_mail" title="E-mail the corresponding author}
• 关键词：arrangement ; zone ; Davenport&ndash ; Schinzel sequence ; inverse Ackermann function
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：221-231
• 全文大小：256 K

文摘

Let L$\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 L$\mathcal{L}$, denoted Z(C,L)$\mathcal{Z}(C,\mathcal{L})$, is defined as the set of all faces in the arrangement A(L)$\mathcal{A}(\mathcal{L})$ that are intersected by C  . Edelsbrunner et al. (1992) showed that the complexity (total number of edges or vertices) of Z(C,L)$\mathcal{Z}(C,\mathcal{L})$ is at most O(nα(n))$O(n\alpha (n))$, where α   is the inverse Ackermann function, by translating the sequence of edges of Z(C,L)$\mathcal{Z}(C,\mathcal{L})$ into a sequence S that avoids the subsequence ababa  . Whether the worst-case complexity of Z(C,L)$\mathcal{Z}(C,\mathcal{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.