如何找到由n个点中选择的三个点确定的最小和最大角度？

Question

给定 n 个二维平面中的点，例如 (0,0),(1,1), ... 我们可以 select 任意三个点从他们来构造角度。比如我们选择A(0, 0), B(1, 1), C (1, 0)，然后我们得到角度 ABC = 45 度，ACB = 90 度和 CAB = 45 度。

我的问题是如何从 n 个点计算由三个点 select 确定的最大或最小角度。

显然，我们可以使用蛮力算法——计算所有角度并找到最大值和最小值，使用余弦定律计算角度，使用勾股定理计算距离。但是高效算法存在吗？

Answer 1

如果我是正确的，蛮力在 O(n^3) 中运行：您基本上取每个三元组，计算 3 个角度，并存储整体最大值。

你可以稍微改进到 O(n^2 * log(n)) 但它更棘手：

best_angle = 0
for each point p1:
    for each point p2:
        compute vector (p1, p2), and the signed angle it makes with the X-axis
        store it in  an array A
    sort array A    # O(n * log(n))
    # Traverse A to find the best choice:
    for each alpha in A:
         look for the element beta in A closest to alpha+Pi 
         # Takes O(log n) because it's sorted. Don't forget to take into account the fact that A represents a circle: both ends touch...
        best_angle = max(best_angle, abs(beta - alpha))

复杂度为O(n * (n + nlog(n) + n * log(n))) = O(n^2 * log(n))

当然你也可以检索循环中获得最佳角度的pt1,pt2

可能还有更好的，这感觉就像做太多的工作，即使你重新使用你以前的 pt1 计算 pt2，...，ptn ...

如何找到由n个点中选择的三个点确定的最小和最大角度？

How to find minimal and maximal angle determined by three points selected from n points?

algorithm

math

geometry

mathematical-optimization