如何有效地找到给定点的最远点(从一组点中)? [英] How to find the farthest point (from a set of points) from a given point efficiently?

问题描述

我正在寻找一种算法或数据结构来解决以下问题:您会得到一组分数S.您还会得到另一种形式的Q查询.对于每个查询，从给定点中查找集合中最远的点.

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.

该集合中最多有10 ^ 5个点，并且有10 ^ 5个查询.点的所有坐标都在0到10 ^ 5之间.

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.

我想知道是否有一种方法可以存储点集，以便我们可以在必要时以O(log n)或O(log ^ 2 n)回答查询.

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.

推荐答案

引自应用程序中最远的邻居"到环形查询":

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

在二维上最远的邻居问题可以在线性空间和对数查询时间中使用点位置来求解最远的Voronoi图(例如，参见de Berg等[5]).

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

其中[5]是指商标教科书":

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

Berg，Mark de，Otfried Cheong，Marc van Kreveld和Mark Overmars.计算几何:算法和应用.Springer-Verlag TELOS，2008年.

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

---

     
     ^{一组最远的邻点Voronoi图.
图片来自Wecom的Jacometti.关于操纵一般细分和计算Voronoi图的原语的注释."(1992).}

这篇关于如何有效地找到给定点的最远点(从一组点中)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！