Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/162710
Title: Expected size of random Tukey layers and convex layers
Authors: Guo, Zhengyang
Li, Yi
Pei, Shaoyu
Keywords: Science::Mathematics
Issue Date: 2022
Source: Guo, Z., Li, Y. & Pei, S. (2022). Expected size of random Tukey layers and convex layers. Computational Geometry, 103, 101856-. https://dx.doi.org/10.1016/j.comgeo.2021.101856
Journal: Computational Geometry
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 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.
URI: https://hdl.handle.net/10356/162710
ISSN: 0925-7721
DOI: 10.1016/j.comgeo.2021.101856
Rights: © 2021 Elsevier B.V. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Page view(s)

7
Updated on Dec 3, 2022

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.