Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868398 | Computational Geometry | 2018 | 12 Pages |
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
Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr, Birgit Vogtenhuber,