Ackerman, Eyal and Keszegh, Balázs and Rote, Günter (2020) An almost optimal bound on the number of intersections of two simple polygons. In: 36th International Symposium on Computational Geometry, SoCG 2020. LeibnizZentrum für Informatik, Wadern. ISBN 9783959771436

Text
2002.pdf Download (1MB)  Preview 
Abstract
What is the maximum number of intersections of the boundaries of a simple mgon and a simple ngon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn − (m + n) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn − (m + dn6 e), for m ≥ n. We prove a new upper bound of mn − (m + n) + C for some constant C, which is optimal apart from the value of C. © Eyal Ackerman, Balázs Keszegh, and Günter Rote; licensed under Creative Commons License CCBY 36th International Symposium on Computational Geometry (SoCG 2020).
Item Type:  Book Section 

Uncontrolled Keywords:  Computational geometry; Ramsey theory; Upper Bound; Combinatorial geometry; Combinatorial geometry; Simple polygon; Simple polygon; Optimal bounds; 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA73 Geometry / geometria 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  07 Sep 2022 14:59 
Last Modified:  27 Apr 2023 08:49 
URI:  http://real.mtak.hu/id/eprint/147954 
Actions (login required)
Edit Item 