License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.8
URN: urn:nbn:de:0030-drops-72008
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7200/
Go to the corresponding LIPIcs Volume Portal

Aichholzer, Oswin ; Balko, Martin ; Hackl, Thomas ; Kyncl, Jan ; Parada, Irene ; Scheucher, Manfred ; Valtr, Pavel ; Vogtenhuber, Birgit

A Superlinear Lower Bound on the Number of 5-Holes

pdf-format:
LIPIcs-SoCG-2017-8.pdf (0.6 MB)

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 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h_5(n) be the minimum number of 5-holes 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 5-hole in P. The proof of this result is computer-assisted.

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 5-Holes}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7200},
  URN =		{urn:nbn:de:0030-drops-72008},
  doi =		{10.4230/LIPIcs.SoCG.2017.8},
  annote =	{Keywords: Erd{\"o}s-Szekeres type problem, k-hole, empty k-gon, empty pentagon, planar point set}
}

Keywords: Erdös-Szekeres type problem, k-hole, empty k-gon, empty pentagon, planar point set
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI