Expected size of random Tukey layers and convex layers

• المؤلفون الرئيسيون: Guo, Zhengyang, Li, Yi, Pei, Shaoyu
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2022
• الموضوعات: Science::Mathematics; Convex Layer; Tukey Depth
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/162710
• المؤسسة: Nanyang Technological University

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.