Algorithm for farthest point query

Правка en1, от 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?).

Теги geometry algorithm, distance


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AnotherRound 2017-02-16 19:39:36 612 Initial revision (published)