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 ?