Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Aichholzer, Oswin; Balko, Martin; Hackl, Thomas; Kyncl, Jan; Parada, Irene; Scheucher, Manfred; Valtr, Pavel; Vogtenhuber, Birgit http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-72008
URL:

; ; ; ; ; ; ;

A Superlinear Lower Bound on the Number of 5-Holes

pdf-format:


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
Seminar: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue date: 2017
Date of publication: 2017


DROPS-Home | Fulltext Search | Imprint Published by LZI