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

id	sg-ntu-dr.10356-162710
record_format	dspace
spelling	sg-ntu-dr.10356-1627102022-11-07T05:03:39Z Expected size of random Tukey layers and convex layers Guo, Zhengyang Li, Yi Pei, Shaoyu School of Physical and Mathematical Sciences Science::Mathematics Convex Layer Tukey Depth 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. 2022-11-07T05:03:39Z 2022-11-07T05:03:39Z 2022 Journal Article 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 0925-7721 https://hdl.handle.net/10356/162710 10.1016/j.comgeo.2021.101856 2-s2.0-85122377116 103 101856 en Computational Geometry © 2021 Elsevier B.V. All rights reserved.
institution	Nanyang Technological University
building	NTU Library
continent	Asia
country	Singapore Singapore
content_provider	NTU Library
collection	DR-NTU
language	English
topic	Science::Mathematics Convex Layer Tukey Depth
spellingShingle	Science::Mathematics Convex Layer Tukey Depth Guo, Zhengyang Li, Yi Pei, Shaoyu Expected size of random Tukey layers and convex layers
description	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.
author2	School of Physical and Mathematical Sciences
author_facet	School of Physical and Mathematical Sciences Guo, Zhengyang Li, Yi Pei, Shaoyu
format	Article
author	Guo, Zhengyang Li, Yi Pei, Shaoyu
author_sort	Guo, Zhengyang
title	Expected size of random Tukey layers and convex layers
title_short	Expected size of random Tukey layers and convex layers
title_full	Expected size of random Tukey layers and convex layers
title_fullStr	Expected size of random Tukey layers and convex layers
title_full_unstemmed	Expected size of random Tukey layers and convex layers
title_sort	expected size of random tukey layers and convex layers
publishDate	2022
url	https://hdl.handle.net/10356/162710
_version_	1749179179467800576

Expected size of random Tukey layers and convex layers

Similar Items