The Expected Number of Extreme Discs
Given a finite set D of n planar discs whose centers are distributed randomly. We are interested in the expected number of extreme discs of the convex hull of D. We show that the expected number of extreme discs is at most O(log2n) for any distribution. This result can be used to derive expected com...
Saved in:
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
H. : ĐHQGHN
2019
|
| Subjects: | |
| Online Access: | http://repository.vnu.edu.vn/handle/VNU_123/64753 https//doi.org/ 10.25073/2588-1124/vnumap.4347 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Vietnam National University, Hanoi |
| Language: | English |
| id |
oai:112.137.131.14:VNU_123-64753 |
|---|---|
| record_format |
dspace |
| spelling |
oai:112.137.131.14:VNU_123-647532019-06-27T07:57:26Z The Expected Number of Extreme Discs Hoang, Dung Nam Nguyen, Kieu Linh VNU Journal of Science: Mathematics – Physics Convex hull Computational geometry Expected number Given a finite set D of n planar discs whose centers are distributed randomly. We are interested in the expected number of extreme discs of the convex hull of D. We show that the expected number of extreme discs is at most O(log2n) for any distribution. This result can be used to derive expected complexity of convex hull algorithms 2019-06-27T07:57:26Z 2019-06-27T07:57:26Z 2019 Article Hoang, D. N., Nguyen, K. L. (2019). The Expected Number of Extreme Discs. VNU Journal of Science: Mathematics – Physics, Vol. 35, No. 2 (2019) 88-93 2588-1124 http://repository.vnu.edu.vn/handle/VNU_123/64753 https//doi.org/ 10.25073/2588-1124/vnumap.4347 en Vol 35;No 2 application/pdf H. : ĐHQGHN |
| institution |
Vietnam National University, Hanoi |
| building |
VNU Library & Information Center |
| country |
Vietnam |
| collection |
VNU Digital Repository |
| language |
English |
| topic |
Convex hull Computational geometry Expected number |
| spellingShingle |
Convex hull Computational geometry Expected number Hoang, Dung Nam Nguyen, Kieu Linh The Expected Number of Extreme Discs |
| description |
Given a finite set D of n planar discs whose centers are distributed randomly. We are interested in the expected number of extreme discs of the convex hull of D. We show that the expected number of extreme discs is at most O(log2n) for any distribution. This result can be used to derive expected complexity of convex hull algorithms |
| author2 |
VNU Journal of Science: Mathematics – Physics |
| author_facet |
VNU Journal of Science: Mathematics – Physics Hoang, Dung Nam Nguyen, Kieu Linh |
| format |
Article |
| author |
Hoang, Dung Nam Nguyen, Kieu Linh |
| author_sort |
Hoang, Dung Nam |
| title |
The Expected Number of Extreme Discs |
| title_short |
The Expected Number of Extreme Discs |
| title_full |
The Expected Number of Extreme Discs |
| title_fullStr |
The Expected Number of Extreme Discs |
| title_full_unstemmed |
The Expected Number of Extreme Discs |
| title_sort |
expected number of extreme discs |
| publisher |
H. : ĐHQGHN |
| publishDate |
2019 |
| url |
http://repository.vnu.edu.vn/handle/VNU_123/64753 https//doi.org/ 10.25073/2588-1124/vnumap.4347 |
| _version_ |
1680962630062178304 |