Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Algorithm for farthest point query

Revision en1, by AnotherRound, 2017-02-16 19:39:36

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?).

Tags geometry algorithm, distance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AnotherRound 2017-02-16 19:39:36 612 Initial revision (published)