Planar point sets determine many pairwise crossing segments

János Pach, Natan Rubin, Gábor Tardos

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

תקציר

We show that any set of n points in general position in the plane determines n1−o(1) pairwise crossing segments. The best previously known lower bound, Ω n, was proved more than 25 years ago by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.

שפה מקוריתאנגלית אמריקאית
כותר פרסום המארחSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
עורכיםMoses Charikar, Edith Cohen
עמודים1158-1166
מספר עמודים9
מסת"ב (אלקטרוני)9781450367059
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 23 יוני 2019
אירוע51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, ארצות הברית
משך הזמן: 23 יוני 201926 יוני 2019

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

שםProceedings of the Annual ACM Symposium on Theory of Computing

כנס

כנס51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
מדינה/אזורארצות הברית
עירPhoenix
תקופה23/06/1926/06/19

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

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