דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

Bottleneck non-crossing matching in the plane

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

2 ציטוטים ‏(Scopus)

תקציר

Let P be a set of 2n points in the plane, and let M C (resp., M NC) denote a bottleneck matching (resp., a bottleneck non-crossing matching) of P. We study the problem of computing M NC. We present an O(n 1.5log 0.5 n)-time algorithm that computes a non-crossing matching M of P, such that bn(M) ≤ 2√10·bnM NC, where bn(M) is the length of a longest edge in M. An interesting implication of our construction is that bn(M NC)/bn(M NC) ≤ 22√10. We also show that when the points of P are in convex position, one can compute M NC in O(n 3) time. (In the full version of this paper, we also prove that the problem is NP-hard and does not admit a PTAS.)

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithms, ESA 2012 - 20th Annual European Symposium, Proceedings
עמודים36-47
מספר עמודים12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2012
פורסם באופן חיצוניכן
אירוע20th Annual European Symposium on Algorithms, ESA 2012 - Ljubljana, סלובניה
משך הזמן: 10 ספט׳ 2012 → 12 ספט׳ 2012

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך7501 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס20th Annual European Symposium on Algorithms, ESA 2012
מדינה/אזורסלובניה
עירLjubljana
תקופה10/09/12 → 12/09/12

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Bottleneck non-crossing matching in the plane'. יחד הם יוצרים טביעת אצבע ייחודית.

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