I recently thought of the following problem: Given a set of N points in the plane(static), we have Q queries. In each query we are given a point with its coordinates and we have to output the point in the set which has maximal distance to the queried point. What is the most efficient algorithm for solving the task(which is not too long/complex to be used in competitions)? Also, what if we could add/remove points from the set? I couldn't think of anything else that bruteforcing every possible point in our set, but I'm looking for something faster(maybe O(logN) per query?).

Please correct me if I made a mistake. I assume that there is no query like insert or remove point from plane.

It's obvious that farthest node must belong to convex hull of those set of points (even if queried point is in inside or outside). So we are storing convex hull points.

Let's say that query point is (

x,y). Make center of coordinate system in that point. We have to deal with every quadrant separately. I think that is not a problem tozonepoints that belong to some quadrant, by simply binary searching them byxandy. For simplicity fix one quadrant, let's say that we fix first. I claim (here is a maybe flaw) that distances from our (x,y) to points in first quadrant increase than decrease, by going in counter clockwise direction, because of convexity of convex hull. These points will form 4 adjacent intervals, which finally means that ternary search is applicable. By doing 4 ternary searches we can find most distant point in for every quadrant and finding quadrants for every point can be done by 4 binary searches in if we store points of convex hull in (counter)clockwise order in structure like`vector`

. That would give us complexity of per query.I'll explain my idea of storing points. Divide convex hull in upper and lower part, which Andrew's monotone chain convex hull algorithm actually does. Store them in

`vector`

. We will maybe have to deal with some corner cases ifxseparator line cross part of upper and lower part of convex hull. I think that binary searching on points stored like I described would be possible.I think that any idea that stick to convex hullcan notsupport dynamic version of this problem since dynamic convex hull can be found in Ω (n).The only problem is that you cannot do a ternary search on such a function.

Wild guess, without proof:

Offline version: compute convex hull, find center point

Cof convex hull (averagex, averagey), sort queries by angle (0, 0) -C, find the furthest point to first query inO(n), move pointer in clockwise direction as you answer queries.Thank you, but I'm looking for an online solution

For the static version take a look at the farthest point Voronoi diagram, it gives you a logarithmic solution. With a standard binary addition trick you can add points at the expense of increasing the complexity by additional log factor. I doubt that the fully online problem with deletions can be properly solved, though.

Could you please provide me an implementation of Voronoi diagram for studying purposes?

Answering to all of you who requested me an implementation: no, I won't give it to you. Me myself not only haven't ever implemented the furthest point Voronoi diagram, but I don't even have an idea how exactly it is built. So, please, use Google. You have all the needed keywords.

Which algorithm would you propose for generating Voronoi diagram?

The most important thing that it should run in O(N*log2(N)) time, of course, another implementations aren't so useful in ACM area.

If it is not too long/complex of course :)

Can you provide a link or do a quick explanation for this version of Voronoi diagram, please.