Aichholzer, Oswin ;
Balko, Martin ;
Hackl, Thomas ;
Kyncl, Jan ;
Parada, Irene ;
Scheucher, Manfred ;
Valtr, Pavel ;
Vogtenhuber, Birgit
A Superlinear Lower Bound on the Number of 5Holes
Abstract
Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5hole in P if H is the vertex set of a convex 5gon containing no other points of P. For a positive integer n, let h_5(n) be the minimum number of 5holes among all sets of n points in the plane in general position.
Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h_5(n) have been of order Omega(n) and O(n^2), respectively. We show that h_5(n) = Omega(n(log n)^(4/5)), obtaining the first superlinear lower bound on h_5(n).
The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line l into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5hole in P. The proof of this result is computerassisted.
BibTeX  Entry
@InProceedings{aichholzer_et_al:LIPIcs:2017:7200,
author = {Oswin Aichholzer and Martin Balko and Thomas Hackl and Jan Kyncl and Irene Parada and Manfred Scheucher and Pavel Valtr and Birgit Vogtenhuber},
title = {{A Superlinear Lower Bound on the Number of 5Holes}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {8:18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7200},
URN = {urn:nbn:de:0030drops72008},
doi = {10.4230/LIPIcs.SoCG.2017.8},
annote = {Keywords: Erd{\"o}sSzekeres type problem, khole, empty kgon, empty pentagon, planar point set}
}
20.06.2017
Keywords: 

ErdösSzekeres type problem, khole, empty kgon, empty pentagon, planar point set 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

20.06.2017 