Expected size of random Tukey layers and convex layers

Expected size of random Tukey layers and convex layers

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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: Guo, Zhengyang, Li, Yi, Pei, Shaoyu
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2022
Subjects:
Science::Mathematics
Convex Layer
Tukey Depth
Online Access:https://hdl.handle.net/10356/162710
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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(kt3log⁡(n/(kt2))). 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.

Similar Items