Expected Size of Random Tukey Layers and Convex Layers

08/05/2020

∙

by   Zhengyang Guo, et al.

∙

0

∙

share

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 O(ktlog(n/k)) and the expected number of vertices on the first t convex layers is O(kt^3log(n/(kt^2))). We also show a lower bound of Ω(tlog n) 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.