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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 23 يونيو 2019
الحدث51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, الولايات المتّحدة
المدة: ٢٣ يونيو ٢٠١٩٢٦ يونيو ٢٠١٩

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing

!!Conference

!!Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
الدولة/الإقليمالولايات المتّحدة
المدينةPhoenix
المدة٢٣/٠٦/١٩٢٦/٠٦/١٩

All Science Journal Classification (ASJC) codes

  • !!Software

قم بذكر هذا