Expected size of random Tukey layers and convex layers

DOI10.1016/J.COMGEO.2021.101856zbMATH Open1486.60020arXiv2008.02258OpenAlexW4206104292MaRDI QIDQ2123288FDOQ2123288

Authors: Zhengyang Guo, Yi Li, Shaoyu Pei 

Publication date: 8 April 2022

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)