Large convex holes in random point sets

József Balogh, Hernán González-Aguilar, Gelasio Salazar

Research output: Contribution to journalArticlepeer-review

Abstract

A convex hole (or empty convex polygon) of a point set P in the plane is a convex polygon with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in the plane. We show that the expected number of vertices of the largest convex hole of a set of n random points chosen independently and uniformly over R is Θ(logn/(loglogn)), regardless of the shape of R.

Original languageEnglish (US)
Pages (from-to)725-733
Number of pages9
JournalComputational Geometry: Theory and Applications
Volume46
Issue number6
DOIs
StatePublished - Aug 1 2013

Keywords

  • Convex hole
  • Erdős–Szekeres Theorem
  • Random point set

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Large convex holes in random point sets'. Together they form a unique fingerprint.

Cite this