Article ID Journal Published Year Pages File Type
6868398 Computational Geometry 2018 12 Pages PDF
Abstract
Considering a typical Erdős-Szekeres-type problem, we show that every 2-convex point set of size n contains an Ω(log⁡n)-hole. In comparison, it is well known that there exist arbitrarily large point sets in general position with no 7-hole. Further, we show that our bound is tight by constructing 2-convex point sets in which every hole has size O(log⁡n).
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , , ,