在二维平面上寻找与一组点的最大距离为最小的点
在二维平面上寻找与一组点的最大距离为最小的点
提问于 2021-03-01 05:31:28
我解决这个问题的方法是将二维平面上的点分解为一维平面上的点，然后分别在x轴和y轴上找到到这些点的最小最大距离(欧几里德距离)的点。对于ex，如果点是{(2,3)，(3,4)，(5,6)}，我将取x坐标(2,3,5)并找到x轴上到这些点的最小最大距离的点，即(2,3,5)，然后取y坐标(3,4,6)并找到y轴上到这些点的最小距离的点，即(3,4,6).My答案将是从该方法获得的(x，y)。但是它在一些测试用例上给出了错误的答案。
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-03-01 08:44:21
你提出的方法是合理的，但并不总是有效的。例如，假设您得到了这些点：(0，-1)，(0，+1)和(1，0)。把你的观点放在最好的地方
P
会是(0，0) -你明白为什么吗？但是，如果您尝试拾取x坐标，使其最小化最大距离为0、0和1，则会选择x= 0.5，这是错误的点。这意味着你需要寻找另一个解决方案。
假设您在2D平面中有一个点集合，并决定拾取某个点
P
作为你的答案。让
问：
其中任何一个点都离得很远
P
尽可能的。然后，如果你画一个圆圈，圆心在
P
这样的话
问：
在该圆的圆周上，则所有其他点要么在该圆内，要么在该圆的圆周上。重点是
P
还必须最小化以这种方式绘制的圆的半径，因为您要最小化与所有可能绘制的圆之间的最大距离
P
任何给定的点。
鉴于此，您正在尝试解决的问题等同于以下问题：
给定一个点集合，包含所有这些点的最小圆是什么？
一旦你有了这个问题的答案，你就可以选择那个圆的圆心作为你的点。
P
..。这个问题被称为
最小圆问题
有许多快速算法可以解决这个问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66414033
复制相关文章
相似问题
腾讯云开发者
