Expected size of random Tukey layers and convex layers

DOI10.1016/J.COMGEO.2021.101856MaRDI QIDQ2123288zbMATH OpenOpenAlexFDO

Authors Zhengyang Guo, Yi Li, Shaoyu Pei

Publication date 8 April 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.02258

zbMATH Keywords

computational geometrygeometric probabilityTukey depthconvex layerTukey layer

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Computational methods for problems pertaining to convex and discrete geometry (52-08)

Abstract: We study the Tukey layers and convex layers of a planar point set, which consists of $n$ points independently and uniformly sampled from a convex polygon with $k$ vertices. We show that the expected number of vertices on the first $t$ Tukey layers is $Oleft(ktlog(n/k)ight)$ and the expected number of vertices on the first $t$ convex layers is $Oleft(k{t}^{3}log(n/(k{t}^2))ight)$. We also show a lower bound of $Omega(tlogn)$ for both quantities in the special cases where $k=3,4$. The implications of those results in the average-case analysis of two computational geometry algorithms are then discussed.

Recommendations

• Maximal and convex layers of random point sets
• On the convex layers of a planar set
• On the convex hull of random points in a polytope
• Counting the onion
• On the expected number of k-sets

Cites work

• scientific article; zbMATH DE number 3541764 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• Algorithms for optimal outlier removal
• Convex bodies, economic cap coverings, random polytopes
• Counting the onion
• Enclosing k points in the smallest axis parallel rectangle
• Maximal and convex layers of random point sets
• On the LLN for the number of vertices of a random convex hull
• On the convex hull of random points in a polytope
• On the convex hull of uniform random points in a simple \(d\)-polytope
• On the convex layers of a planar set
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Shape Fitting with Outliers
• Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• Sylvester's question: The probability that \(n\) points are in convex position
• The convex floating body and polyhedral approximation
• The convex hull of a normal sample
• The convex hull of a random set of points
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten

Cited in

(2)

• Maximal and convex layers of random point sets
• The layer number of \(\alpha \)-evenly distributed point sets

This page was built for publication: Expected size of random Tukey layers and convex layers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123288)