GEOCHEAT - Editorial

convex
convex-hull
editorial
geocheat
geometry
hard
oct16
random

#1

PROBLEM LINKS

Practice
Contest

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
ext{Upon expansion, we get } T(n) = (n + \frac{2 n}{3} + \frac{4 n}{9} + .. + 1) imes 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.

EXPLANATION

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

EDITORIALIST’S SOLUTION

Can be found here.


#2

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.”


#3

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?


#4

I wanted to know what was the approach for 50 points?

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).


#5

i am new to this site so can anyone tell where to start…??


#6

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?


#7

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.