On the zone of a circle in an arrangement of lines

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

1 ציטוט ‏(Scopus)

תקציר

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.

שפה מקוריתאנגלית
עמודים (מ-עד)221-231
מספר עמודים11
כתב עתElectronic Notes in Discrete Mathematics
כרך49
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - נוב׳ 2015

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the zone of a circle in an arrangement of lines'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי