maximum distance in between points in taxicab metrics - inserting and deleting points
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:


You can iterate over all possible choices for the first point $(x_i, y_i)$.
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 &lt;= 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?