A Note on the Number of General 4-holes in (Perturbed) Grids

Oswin Aichholzer, Thomas Hackl, Pavel Valtr, Birgit Vogtenhuber

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


Considering a variation of the classical Erdos-Szekeres type problems, we count the number of general 4-holes (not necessarily convex, empty 4-gons) in squared Horton sets of size $ntimesn$. Improving on previous upper and lower bounds we show that this number is $n^2log n)$, which constitutes the currently best upper bound on minimizing the number of general $4$-holes for any set of $n$ points in the plane. To obtain the improved bounds, we prove a result of independent interest. We show that $d=1^n d)d^2 = log n)$, where $d)$ is Euler's phi-function, the number of positive integers less than~$d$ which are relatively prime to $d$. This arithmetic function is also called Euler's totient function and plays a role in number theory and cryptography.
Original languageEnglish
Title of host publicationDiscrete and Computational Geometry and Graphs. JCDCGG 2015.
EditorsJin Akiyama, Hiro Ito, Toshinori Sakai, Yushi Uno
PublisherSpringer, Cham
Number of pages12
ISBN (Print)978-3-319-48531-7
Publication statusPublished - 2016
EventJapanese Conference on Discrete and Computational Geometry and Graphs: JCDCGG 2015 - Kyoto, Japan
Duration: 14 Sept 201516 Sept 2015

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham


ConferenceJapanese Conference on Discrete and Computational Geometry and Graphs

Fields of Expertise

  • Information, Communication & Computing

Cite this