线性算法在点集中找到具有至少一半直径距离的两个点
Linear algorithm to find two points with at least half diameter distance in a point set
我遇到了以下作业问题：
Consider a point set P in the plane with |P| = n and let D(P) the diameter of P, i.e. the maximum Euclidean distance between any two points in P. I am tasked to find an algorithm of O(n) time that on input of P returns two points x and y of P with d(x,y) >= D(P)/2, where d denotes the Euclidean distance.
我不知道我该怎么做。你能给我一个提示吗？
假设您的积分是 (xi,yi)
- 找到
min(xi) 和 O(n) 的点并将其命名为 minX_point
- 找到
max(xi) 和 O(n) 的点并将其命名为 maxX_point
- 找到
min(yi) 和 O(n) 的点并将其命名为 minX_point
- 找到
max(yi) 和 O(n) 的点并将其命名为 maxY_point
现在考虑矩形框这4个点（水平和垂直边缘）
该矩形的直径大于或等于 D(P)，因为所有 P 点都包含在其中。
长方形的直径如下
Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2)
现在找到 max((mixX-maxX),(minY-maxY))
最大值将是您想要的点，例如 maxX_point 和 minX_point
因为如果距离小于 D(P)/2 那么我们有
Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2) < sqrt((D(P)/2)^2+(D(P)/2)^2)=D(P)/sqrt(2) Rec_Diameter>=D(P) < D(P)/sqrt(2) 不正确
我遇到了以下作业问题：
Consider a point set P in the plane with |P| = n and let D(P) the diameter of P, i.e. the maximum Euclidean distance between any two points in P. I am tasked to find an algorithm of O(n) time that on input of P returns two points x and y of P with d(x,y) >= D(P)/2, where d denotes the Euclidean distance.
我不知道我该怎么做。你能给我一个提示吗？
假设您的积分是 (xi,yi)
- 找到
min(xi)和O(n)的点并将其命名为minX_point - 找到
max(xi)和O(n)的点并将其命名为maxX_point - 找到
min(yi)和O(n)的点并将其命名为minX_point - 找到
max(yi)和O(n)的点并将其命名为maxY_point
现在考虑矩形框这4个点（水平和垂直边缘）
该矩形的直径大于或等于 D(P)，因为所有 P 点都包含在其中。
长方形的直径如下
Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2)
现在找到 max((mixX-maxX),(minY-maxY))
最大值将是您想要的点，例如 maxX_point 和 minX_point
因为如果距离小于 D(P)/2 那么我们有
Rec_Diameter=sqrt((minX-maxX)^2+(minY-maxY)^2) < sqrt((D(P)/2)^2+(D(P)/2)^2)=D(P)/sqrt(2) Rec_Diameter>=D(P) < D(P)/sqrt(2) 不正确