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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - نوفمبر 2015

بصمة

أدرس بدقة موضوعات البحث “On the zone of a circle in an arrangement of lines'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا