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...
Saved in:
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | Article |
| 語言: | English |
| 出版: |
2022
|
| 主題: | |
| 在線閱讀: | https://hdl.handle.net/10356/162710 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 總結: | 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 Ω(tlogn) 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. |
|---|