1
$\begingroup$

Let's define distance (taxicab metrics) between two points $(x_1, y_1)$ and $(x_2, y_2)$ as $$|x_2-x_1| + |y_2-y_1|$$

Initially, there are given empty set of points.
I think how to find maximum distance between two arbitrary points (among inserted points). Possible operations are:
1. Insert point
2. Delete point
3. Find maximum distance (taxicab metrics) between two points.

I can do it using AVL tree (augmenting). Then I can insert and delete point in $O(\log n)$, whereas find costs $O(n\log n)$ where $n$ is number of points.

However, I consider is it possible to speed up operation Find.
Any ideas ?

$\endgroup$
2
$\begingroup$

Yes, I think you can get $O(\log n)$ for $find()$ too.

First, figure out how to implement $find()$ in $O(n)$ time. Here are some ideas:

  1. You can iterate over all possible choices for the first point $(x_i, y_i)$.

  2. Now the problem is that depending on where the other points are situated in relation to $(x_i, y_i)$ the distance formula can take $4$ different forms. Each one of them entails different signs for the coordinates. We don't know where the maximum will come from, so let's iterate over all $4$ cases. Let's say the first case is $(x_i, -y_i)$. You'll have to match this with a $(-x_j, y_j)$, and you'll want to match it with one that has the maximum sum $-x_j + y_j$. Your first concern is how to obtain this best sum in $O(1)$. Your second concern is convincing yourself this solution is correct, because nowhere have we made sure that the best $(-x_j, y_j)$ actually has $x_j <= x_i$ so that $|x_i - x_j| = x_i - x_j$. We're trying to maximize the result of each case, but we're taking all points into account for all $4$ cases, disregarding their position relative to the fixed point. Can you see why this actually works?

$\endgroup$
  • $\begingroup$ I didn't manged to understand your idea. $\endgroup$ – user40545 Dec 29 '15 at 13:39
  • $\begingroup$ Can you be more specific? What part is unclear? $\endgroup$ – Mihai Dec 29 '15 at 14:27
  • $\begingroup$ Your idea is uncler for me. You are going to consider each point, let's take $t=(x_i, y_i)$. Then, you consider 4 cases: on the left, right, under, above $t$. Is it your idea ? $\endgroup$ – user40545 Dec 29 '15 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.