Charles Explorer logo
🇨🇿

Holes in 2-Convex Point Sets

Publikace na Matematicko-fyzikální fakulta |
2018

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

Let S be a set of n points in the plane in general position (no three points from S are collinear). For a positive integer k, a k-hole in S is a convex polygon with k vertices from S and no points of S in its interior.

For a positive integer l, a simple polygon P is l-convex if no straight line intersects the interior of P in more than l connected components. A point set S is l-convex if there exists an l-convex polygonization of S.

Considering a typical Erd. os-Szekeres-type problem, we show that every 2-convex point set of size n contains an Omega(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 with holes of size at most O(log n).