GEOCHEAT Editorial

dpraveen · October 17, 2016, 2:48am

PROBLEM LINKS

DIFFICULTY

hard

PREREQUISITES

random, expected value, convex hull, rotating callipers

PROBLEM

You 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 EXPLANATION

Let S_i denote the set of points p_1, p_2, \dots, p_i.

Think in reverse

The 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 solution

Let 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 non-bitonic

Let 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 anti-clockwise 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.