Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
可以通过拉伸橡皮筋找到凸面外壳，使其包含所有点，然后释放它。
所以我的问题是：假设我们有一个机器人（理论机器人）来解决这个问题。
我们给它点的坐标（我们有n个点）。
它使用一些管脚来指示电路板（o（n））中的点。
现在我们选择一个点（我们选择哪个点并不重要），然后我们检查它与其他点的距离，比如（sqr（x^2+y^2））。我们找到最大距离。
然后，机器人使用橡皮筋，以圆的形式将其延伸，半径为我们在步骤2中找到的距离，并以我们在步骤2中选择的点为中心。它释放了乐队。
然后机器人需要跟随橡皮筋在o（m）中找到凸壳的顶点，其中m是凸壳由它们组成的顶点（m所以算法的总阶数（这样）是O（n）。
我知道我没有考虑到橡皮筋需要拉伸的时间或收缩的时间。
但假设我们有很多点，它（收缩/拉伸）比O（n）要少得多。
电脑里有没有模拟橡皮筋的效果？
我知道凸壳的最低可能阶是o（nlg（n）），这是由于排序较低的频带。
最佳答案
我想你可以用某种优化算法来模拟“橡皮筋算法”，但它可能会非常慢。请记住，在某种意义上，物理世界是一个巨大的，极其复杂的计算机，一直在计算复杂的东西，如重力，磁力等，最后但不是碰撞检测。
首先，让我们进行设置：
橡皮筋被表示为一个双链接的节点列表，其中包含橡皮筋中每个“原子”的位置（将橡皮筋视为一维原子链）
管脚由某种空间映射或非常细粒度的n维数组表示，该数组保存某个小区域是否包含管脚的信息
现在，实际的算法：
当橡皮筋中的“原子”接触/非常接近一根针时（根据空间地图或n-d数组），该原子就被固定，不能再移动
对于所有其他原子，稍微改变它们的位置，以最小化到它们各自相邻原子的距离；您可以使用随机优化或群算法来实现这一点
重复直到所有的原子都“稳定下来”
当然，这种算法的复杂性是可怕的，远比O（n）甚至O（nLogn）差很多，因为“橡皮筋”的昂贵计算通常是由称为宇宙的巨大物理引擎来执行的。（通过将“橡皮筋和钉板”问题输入到任何现代物理模拟中，都可能获得类似的结果。）