返回题库

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

HMMT February 2020 — Guts Round — Problem 35

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [22] A collection S of 10000 points is formed by picking each point uniformly at random inside a circleof 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.
解析

英文解析

  1. [22] A collection S of 10000 points is formed by picking each point uniformly at random inside a circleof 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.