PROBLEM LINK:
Author: Jatin Yadav
Tester: tncks0121
DIFFICULTY:
Easy
PREREQUISITES:
Geometry, Linearity of expectation
PROBLEM:
Given a convex polygon P. On each edge, chose a random point. Find the expected area of the convex hull of the chosen points.
QUICK EXPLANATION:
The answer is the area of the polygon whose vertices are the midpoints of the original polygon P
EXPLANATION:
Please note that all the subscripts in the following discussion have to be considered modulo n.
First, notice that the chosen points will be convex. So, we just need to find the expected area of the convex polygon with vertices R_0, R_2, \ldots R_{n-1} in anticlockwise order.
We know that the area would be A = \dfrac{1}{2} \displaystyle \sum R_i \times R_{i + 1}
So, E[A] = \dfrac{1}{2} \displaystyle \sum E[ R_i \times R_{i + 1}]
For each i, R_i = t_i P_{i} + (1 - t_i) P_{i+1} , where t_i is chosen uniformly at random in the range [0, 1].
Therefore, E[A] = \dfrac{1}{2} \displaystyle \sum E[ (t_i P_{i} + (1 - t_i) P_{i+1}) \times (t_{i+1} P_{i + 1} + (1 - t_{i+1}) P_{i+2})]
= \dfrac{1}{2} \displaystyle \sum ( E[t_i t_{i + 1}] P_i \times P_{i+ 1} + E[t_i (1 - t_{i + 1})] P_i \times P_{i +2} + E[(1 - t_i) t_{i + 1}] P_{i + 1} \times P_{i + 1} + E[(1 - t_i) (1 - t_{i + 1})] P_{i + 1} \times P_{i + 2}
As t_i and t_{i + 1} are independent, all the expected values involved are \frac{1}{2} \times \frac{1}{2} = \frac{1}{4} .
Replacing the E[] values by \frac{1}{4} and rearranging into a single cross product, we have:
So, E[A] = \displaystyle \sum \left (\left (\dfrac{P_i + P_{i + 1}}{2} \right ) \times \left (\dfrac{P_{i+1} + P_{i + 2}}{2} \right) \right) .
This means that we can just assume R_i to be the midpoint of P_i and P_{i + 1} and then find the area, and that would be the answer.
AUTHOR’S and TESTER’S codes:
The author’s code can be found here
The tester’s code can be found here