使用橡皮筋求解凸包？
Convex hull solving using a rubber band?
可以通过拉伸橡皮筋使其包含所有点然后松开来找到凸包。
所以我的问题是：假设我们有一个机器人（理论上的机器人）来解决这个问题。
我们给它我们点的坐标（我们有 n 个点）。
它使用一些引脚来指示板上的点 (O(n))。
现在我们选择一个点（选择哪个并不重要）然后我们检查它与其他点的距离，例如 ( sqr( x^2 + y^2 ) ) 。然后我们找到最大距离。
然后机器人用一根橡皮筋将它拉长成一个圆，其半径为我们在第2步中找到的距离，并以我们在第2步中选择的点为中心。它释放了乐队 。
然后机器人需要跟随橡皮筋在O(m)中找到凸包的顶点，其中m是凸包由它们组成的顶点。(m <= n)
所以算法的总阶数（这种方式）为 O(n)。
我知道我没有考虑橡皮筋需要拉伸的时间或收缩所需的时间。
但假设我们有很多点，它 (contraction/streching) 比 O(n) 少得多。
有没有电脑模拟橡皮筋的效果？
我知道凸包的最低可能顺序据说是 O(nlg(n)) 由于排序较低带。
but assuming we have lots of points it takes much less than O(n).
不，不是，因为这一步：
Now we choose a point (it's not important which one we choose) then we check its distance with other points like ( sqr( x^2 + y^2 ) ) . And we find the Max distance .
您无法在小于 O(n) 的时间内找到此最大距离。
还有：
Then the robot uses a rubber band and extends it in form of a circle with a radius of distance we found in step 2 and centered in the point we chose in step 2. And it releases the band .
Then the robot needs to follow the rubber band to find the vertices of the convex hull in O( m ) where m is the vertices that convex hull consists of them.(m <= n)
这需要 O(m*n) 时间，参见 Jarvis march 算法。需要确认每个点都是凸包的一部分，不能把松紧带拉一下就完事了
"is there anyway to simulate the effect of the rubber band in computer"：不，不是关于计算复杂性。计算机操作一次处理恒定数量的操作数。例如，典型的凸包算法会三个三个地取点，并检查它们是否形成顺时针或逆时针三角形。据说这是在恒定时间内完成的。
释放波段涉及所有N点，不能作为原始操作实现。
如果您尝试以某种方式用计算机模拟它，您可以确定它至少需要 O(N Log(N)) 次操作。无论如何，在离散宇宙（整数坐标）中，O(N) 可以使用基数排序。
我猜你可以使用某种优化算法来模拟"rubber band algorithm"，但它可能会非常慢。请记住，从某种意义上说，物理世界是一台巨大的、极其复杂的计算机，一直在计算复杂的东西，如重力、磁力等，最后但不是碰撞检测。
首先，让我们进行设置：
- 橡皮筋表示为节点的双向链表，其中包含每个 "atom" 在橡皮筋中的位置（将橡皮筋视为一维原子链）
- 引脚由某种空间图或非常细粒度的 n 维数组表示，其中包含某个小区域是否包含引脚的信息
现在，实际算法：
- 每当橡皮筋中的 "atom" touches/is 非常靠近一个引脚（根据空间图或 n-d 数组）时，该原子是固定的并且不能再移动
- 对于所有其他原子，稍微改变它们的位置以最小化到它们各自相邻邻居的距离；您可以使用例如随机优化或群算法来做到这一点
- 重复直到所有原子都"settled down"
当然，这个算法的复杂度很可怕，比O(n)甚至O(nlogn)都差远了，因为 "rubber band" 的所有昂贵计算通常都是由称为宇宙的伟大物理引擎执行的。 （通过将 "rubber band and board of pins" 问题输入任何现代物理模拟，您可能会获得类似的结果。）
可以通过拉伸橡皮筋使其包含所有点然后松开来找到凸包。
所以我的问题是：假设我们有一个机器人（理论上的机器人）来解决这个问题。 我们给它我们点的坐标（我们有 n 个点）。
它使用一些引脚来指示板上的点 (O(n))。
现在我们选择一个点（选择哪个并不重要）然后我们检查它与其他点的距离，例如 ( sqr( x^2 + y^2 ) ) 。然后我们找到最大距离。
然后机器人用一根橡皮筋将它拉长成一个圆，其半径为我们在第2步中找到的距离，并以我们在第2步中选择的点为中心。它释放了乐队 。
然后机器人需要跟随橡皮筋在O(m)中找到凸包的顶点，其中m是凸包由它们组成的顶点。(m <= n)
所以算法的总阶数（这种方式）为 O(n)。
我知道我没有考虑橡皮筋需要拉伸的时间或收缩所需的时间。
但假设我们有很多点，它 (contraction/streching) 比 O(n) 少得多。
有没有电脑模拟橡皮筋的效果？
我知道凸包的最低可能顺序据说是 O(nlg(n)) 由于排序较低带。
but assuming we have lots of points it takes much less than O(n).
不，不是，因为这一步：
Now we choose a point (it's not important which one we choose) then we check its distance with other points like ( sqr( x^2 + y^2 ) ) . And we find the Max distance .
您无法在小于 O(n) 的时间内找到此最大距离。
还有：
Then the robot uses a rubber band and extends it in form of a circle with a radius of distance we found in step 2 and centered in the point we chose in step 2. And it releases the band .
Then the robot needs to follow the rubber band to find the vertices of the convex hull in O( m ) where m is the vertices that convex hull consists of them.(m <= n)
这需要 O(m*n) 时间，参见 Jarvis march 算法。需要确认每个点都是凸包的一部分，不能把松紧带拉一下就完事了
"is there anyway to simulate the effect of the rubber band in computer"：不，不是关于计算复杂性。计算机操作一次处理恒定数量的操作数。例如，典型的凸包算法会三个三个地取点，并检查它们是否形成顺时针或逆时针三角形。据说这是在恒定时间内完成的。
释放波段涉及所有N点，不能作为原始操作实现。
如果您尝试以某种方式用计算机模拟它，您可以确定它至少需要 O(N Log(N)) 次操作。无论如何，在离散宇宙（整数坐标）中，O(N) 可以使用基数排序。
我猜你可以使用某种优化算法来模拟"rubber band algorithm"，但它可能会非常慢。请记住，从某种意义上说，物理世界是一台巨大的、极其复杂的计算机，一直在计算复杂的东西，如重力、磁力等，最后但不是碰撞检测。
首先，让我们进行设置：
- 橡皮筋表示为节点的双向链表，其中包含每个 "atom" 在橡皮筋中的位置（将橡皮筋视为一维原子链）
- 引脚由某种空间图或非常细粒度的 n 维数组表示，其中包含某个小区域是否包含引脚的信息
现在，实际算法：
- 每当橡皮筋中的 "atom" touches/is 非常靠近一个引脚（根据空间图或 n-d 数组）时，该原子是固定的并且不能再移动
- 对于所有其他原子，稍微改变它们的位置以最小化到它们各自相邻邻居的距离；您可以使用例如随机优化或群算法来做到这一点
- 重复直到所有原子都"settled down"
当然，这个算法的复杂度很可怕，比O(n)甚至O(nlogn)都差远了，因为 "rubber band" 的所有昂贵计算通常都是由称为宇宙的伟大物理引擎执行的。 （通过将 "rubber band and board of pins" 问题输入任何现代物理模拟，您可能会获得类似的结果。）