Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find the farthest point (from a set of points) from a given point efficiently?

I'm looking for an algorithm or data structure to solve the following problem: You are given a set of points S. And you are given Q queries in form of another point. For every query, find the farthest point in the set from the given point.

There are at most 10^5 points in the set and 10^5 queries. All the coordinates for points are in range from 0 to 10^5.

I am wondering if there is a way to store the set of points such that we can answer the queries in O(log n) or O(log^2 n) if necessary.

like image 873
Nikola Pesic Avatar asked Jan 11 '19 20:01

Nikola Pesic


1 Answers

A quote from "Approximate Furthest Neighbor with Application to Annulus Query":

In two dimensions the furthest neighbor problem can be solved in linear space and logarithmic query time using point location in a furthest point Voronoi diagram (see, for example, de Berg et al. [5]).

where [5] refers to the "Marks textbook":

Berg, Mark de, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer-Verlag TELOS, 2008.


          Fig
          Farthest-Neighbor Voronoi diagram for a set of eight points.
Image from Jacometti, Welson. "A Note on Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams." (1992).

like image 191
Joseph O'Rourke Avatar answered Nov 16 '22 00:11

Joseph O'Rourke