PROBLEM LINKSDIFFICULTYhard PREREQUISITESrandom, expected value, convex hull, rotating callipers PROBLEMYou are $n$ points $p_1, p_2, \dots, p_n$ in 2D plane. Assume that the order of these points is randomly shuffled. Problem asks you to find out diameter of set of points when you add the points in the order left to right, one by one. QUICK EXPLANATIONLet $S_i$ denote the set of points $p_1, p_2, \dots, p_i$. Think in reverseThe idea is to remove points instead of adding. Assume initially all the points $p_1, p_2, \dots p_n$ are present. The diameter of all these points can be find in $\mathcal{O}(n \, logn)$ by applying rotating callipers technique over the convex hull of the points. Let the pair of points which form a diameter (if they are more than one, break the ties arbitrarily) be $p_i, p_j$. As the indices of the points are uniformly randomly shuffled. So the expected value of $max(i, j)$ will be $\frac{2 n}{3}$. So, this means even if you remove the points $p_k$, s.t. $k > max(i, j)$ , the diameter won't be changed. So, the diameters for $S_k, S_{k + 1}, S_n$ will be same as the diameter of all the points, where $k = max(i, j) + 1$. We keep doing this till we remove all the points. Time Complexity of the solutionLet $T(n)$ denote the time to find the diameters of $S_1, S_2, \dots, S_n$. We get the expressions. $$T(n) = T(\frac{2 n}{3}) + \mathcal{O}(n \, logn)$$ $$T(\frac{2 n}{3}) = T(\frac{4 n}{9}) + \mathcal{O}(\frac{2 n}{3} \cdot logn)$$ $$..$$ $$..$$ $$T(1) = 1$$ $$\text{Upon expansion, we get } T(n) = (n + \frac{2 n}{3} + \frac{4 n}{9} + .. + 1) \times log(n)$$ You can estimate expression $(n + \frac{2 n}{3} + \frac{4 n}{9} + .. + 1)$ as follows. We can bound its value by summing this geometric progression for infinite terms. Sum of an infinite series $$a + a \cdot r + a \cdot r^2 + \dots + \infty$$ is given by $\frac{a}{1  r}$. Note that this sum converges to finite value if $r < 1$. In our case, $r = \frac{2}{3}$. So, sum of infinite searies $$(n + \frac{2 n}{3} + \frac{4 n}{9} + \dots + \infty$$ will be $$\frac{n}{(1  \frac{2}{3})} = \frac{n}{\frac{1}{3}}$$ $$= \mathcal{O}(n)$$ Hence overall time complexity comes out to be randomized $\mathcal{O}(n \, logn)$ overall. A comment regarding distance function of points from a point on convex polygon being nonbitonicLet $x$ be a fixed point on a convex polygon. Let $f(y)$ denote the distance between points $x$ and $y$. It might seem to you if you iterate from $y$ from point $x$ to other points in anticlockwise direction, the value of function $f(y)$ will first increase and then decrease, i.e. function $f(y)$ is bitonic, i.e. a ternary search might be applied for finding the farthest point. But it is not true. The function $f(y)$ is not bitonic. Let us see a counter example for this. Imagine a big circle. The point $x$ is the center of the circle. Now, you can draw a polygon in such a way that the adjacent vertices alternate between belonging to circle, and not belonging to circle. This makes the distance function to increase, decrease, increase, decrease as many times as you want. This breaks the bitonicity. EXPLANATIONSETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here. EDITORIALIST'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Oct '16, 12:39

If points are generated randomly, the expected size of the convex hull is very small (link). As you add points one by one, you can assume that the convex hull size won't exceed 40. For every new point you should recalculate the hull with one more point (if the size was k, you recalculate the hull on k+1 points). My code on ideone: link (focus on the main() function). answered 19 Oct '16, 20:33

Could you please explain the statement "As the indices of the points are uniformly randomly shuffled. So the expected value of max(i,j) will be 2n/3." answered 19 Oct '16, 13:17

I wanted to know what was the approach for 50 points? Many people have scored 50. How do you use the given property for subtask 2? answered 19 Oct '16, 19:37

i am new to this site so can anyone tell where to start..?? answered 19 Jun '17, 06:49

I want to know how did you get that 50 points in the end? I mean, it wasn't my answer when I calculated. Many of my friends (from thesis writing help) also got 50 but I seem to find some error. How did you use the property in subtask 2? answered 29 Aug '17, 18:29

The distance learning is now viral and very important for all students who want to grow fast with the online degree in UAE. A brother of my friend is also finished his MBA degree from an online university with innovative courses and after degree process, he gets a work in a very big organization for his bright future. answered 14 Dec '17, 14:31
