HMMT 二月 2020 · 冲刺赛 · 第 35 题

HMMT February 2020 — Guts Round — Problem 35

[22] A collection S of 10000 points is formed by picking each point uniformly at random inside a circle of radius 1. Let N be the expected number of points of S which are vertices of the convex hull of the S . (The convex hull is the smallest convex polygon containing every point of S .) Estimate N . An estimate of E > 0 will earn max( b 22 − | E − N |c , 0) points.

解析

[22] A collection S of 10000 points is formed by picking each point uniformly at random inside a circle of radius 1. Let N be the expected number of points of S which are vertices of the convex hull of the S . (The convex hull is the smallest convex polygon containing every point of S .) Estimate N . An estimate of E > 0 will earn max( b 22 − | E − N |c , 0) points. Proposed by: Shengtong Zhang Answer: ≈ 72 . 8 Solution: Here is C++ code by Benjamin Qi to estimate the answer via simulation. It is known that the expected number of vertices of the convex hull of n points chosen uniformly at random inside a 1 / 3 circle is O ( n ). See “On the Expected Complexity of Random Convex Hulls” by Har-Peled.