Presentation
Empty convex polytopes in random point sets
Author/s | Balogh, József
González Aguilar, Hernán Salazar Anaya, Gelasio |
Editor | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Publication Date | 2013 |
Deposit Date | 2017-05-22 |
Published in |
|
Abstract | 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 ... 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. |
Project ID. | DMS-0745185
106432 |
Citation | Balogh, J., González Aguilar, H. y Salazar Anaya, G. (2013). Empty convex polytopes in random point sets. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Empty convex polytopes in random ... | 916.1Kb | [PDF] | View/ | |