文章基本信息

标题：An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons
本地全文：下载
作者：Eyal Ackerman ; Bal{'a}zs Keszegh ; G{"u}nter Rote 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：1:1-1:18
DOI：10.4230/LIPIcs.SoCG.2020.1
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, 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 + âO^ n/6 âO), 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.
关键词：Simple polygon; Ramsey theory; combinatorial geometry