×

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.

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

# EDITORIALIST'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 5 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). answered 19 Oct '16, 20:33 990●2●18 accept rate: 30%
 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." answered 19 Oct '16, 13:17 6★likecs 3.7k●24●81 accept rate: 9%
 2 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 6★ankesh18 627●1●11 accept rate: 7%
 0 i am new to this site so can anyone tell where to start..?? answered 19 Jun '17, 06:49 1 accept rate: 0%
 0 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 1 accept rate: 0%
 0 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 -1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×647
×153
×63
×49
×20
×4

question asked: 19 Oct '16, 12:39

question was seen: 3,628 times

last updated: 14 Dec '17, 14:31