algorithm - 找到一个点，该点与有界区域内的一组点的总距离最大

Question

给定一组点 p，我想在空间 b 中找到一个点，它限制了 p 的区域，即尽可能远离 p 内的所有点。

这是关于根据 Craig Reynolds' Boids 在植绒模拟中实现邻居避免的- 如果这不是避开邻居的最佳方式，我会喜欢建议。

编辑:换句话说，我想找到一个尽可能远离 p 中其他点的任意点，同时保持在 p 周围的边界框内。

我所说的边界框是指解决方案应该是一个点，该点的 y 坐标介于最高点和最低点之间，x 坐标介于最左边和最右边的点之间。

为了更抽象地提出这个问题，我将此算法视为一种为代理找到目标的方法，该代理希望保持在其最近邻居的 M 单位内，同时不接近 m 个单位。该算法返回的解应该返回一个与其最近的邻居之间距离最大的点。

这是在二维平面中。

Answer 1

听起来解决方案必须位于(其他)代理的 Voronoi 图的交点之一。因此，一种算法解决方案是构建 Voronoi 图，迭代交叉点，并选择与邻居的最短距离最大的交叉点。