maximum distance in between points in taxicab metrics - inserting and deleting points

Question

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 ?

Answer 1

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?