Published May 22, 2017 | Version v1
Publication Metadata-only

Empty convex polytopes in random point sets

Creators

Contributors

Description

Given a set P of points in Rd, a convex hole (alternatively, empty convex polytope) of P is a convex polytope with vertices in P, containing no points of P in its interior. Let R be a bounded convex region in Rd. We show that if P is a set of n random points chosen independently and uniformly over R, then the expected number of vertices of the largest hole of P is Θ(log n/(log log n)), regardless of the shape of R. This generalizes the analogous result proved for the case d = 2 by Balogh, González-Aguilar, and Salazar.

Abstract

National Science Foundation

Abstract

Programa del Mejoramiento del Profesorado (PROMEP)

Abstract

Consejo Nacional de Ciencia y Tecnología (México)

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/60155
URN
urn:oai:idus.us.es:11441/60155

Origin repository

Origin repository
USE