Large convex holes in random point sets

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

doi:10.1016/j.comgeo.2012.11.004

Large convex holes in random point sets

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

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	725-733
Number of pages	9
Journal	Computational Geometry: Theory and Applications
Volume	46
Issue number	6
DOIs	https://doi.org/10.1016/j.comgeo.2012.11.004
State	Published - 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

Online availability

10.1016/j.comgeo.2012.11.004

Library availability

Discover UIUC Full Text

Cite this

@article{b25969bdbddd440680b697e9dad82631,

title = "Large convex holes in random point sets",

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.",

keywords = "Convex hole, Erd{\H o}s–Szekeres Theorem, Random point set",

author = "J{\'o}zsef Balogh and Hern{\'a}n Gonz{\'a}lez-Aguilar and Gelasio Salazar",

note = "Publisher Copyright: {\textcopyright} 2012 Elsevier B.V.",

year = "2013",

month = aug,

day = "1",

doi = "10.1016/j.comgeo.2012.11.004",

language = "English (US)",

volume = "46",

pages = "725--733",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Large convex holes in random point sets

AU - Balogh, József

AU - González-Aguilar, Hernán

AU - Salazar, Gelasio

PY - 2013/8/1

Y1 - 2013/8/1

N2 - 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.

AB - 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.

KW - Convex hole

KW - Erdős–Szekeres Theorem

KW - Random point set

UR - http://www.scopus.com/inward/record.url?scp=84992521744&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84992521744&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2012.11.004

DO - 10.1016/j.comgeo.2012.11.004

M3 - Article

AN - SCOPUS:84992521744

SN - 0925-7721

VL - 46

SP - 725

EP - 733

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 6

ER -

Large convex holes in random point sets

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this