凸包可以通过拉伸橡皮筋找到，使其包含所有点并释放它。使用橡皮筋解决凸壳？
所以我的问题是：让我们假设我们有一个机器人（理论机器人）来解决这个问题。 我们给它的坐标（我们有n点）。
它使用一些引脚来指示板上的点（O（n））。现在我们选择一个点（它并不重要，我们选择哪一个），然后我们检查它与其他点的距离，如（sqr（x^2 + y^2））。我们找到最大距离。
然后，机器人使用一个橡皮筋，并以步骤2中找到的具有半径距离的圆的形式将其延伸，并在步骤2中选择的点的中心。然后释放该带。
然后，机器人需要遵循橡皮筋找到的凸包的顶点在O（m），其中m是该凸包包含它们的顶点。（米< = N）
所以算法的总顺序（这种方式）应该是O（n）。
我知道我没有考虑到橡皮筋需要拉伸的时间或需要收缩的时间。
但假设我们有很多点（收缩/拉伸）比O（n）要少得多。
有无论如何模拟橡皮筋在电脑中的效果？
我知道由于排序低频带，凸包的最低可能顺序被认为是O（nlg（n））。
我想你可能模仿使用某种优化算法的“橡皮筋算法”，但它可能会非常慢。请记住，从某种意义上说，物理世界是一个巨大的，非常复杂的计算机，一直在计算复杂的东西，比如重力，磁力等，最后但不是碰撞检测。
首先，让我们做的设置：
现在，实际算法：
当然，这种算法的复杂性是可怕的，远远超过糟糕，你可以用，例如，随机优化或群算法
但假设我们有很多点，它比O（n）要少得多。
不，它不需要，因为这一步的：
现在，我们选择一个点（这并不重要，我们选择哪一个），那么要检查它的距离与其它点状（SQR（X^2 + y^2））。我们找到最大距离。
无法找到此最大距离小于O(n)。
另外：
然后，机器人使用的橡胶带，它与我们在步骤2中找到的距离的半径的圆的形式延伸，并在中心我们在步骤2中它选择的点释放乐队。
然后机器人需要按照橡皮筋找到O（m）中凸包的顶点，其中m是凸包由它们组成的顶点。（米< = N）
这需要O(m*n)时间，见Jarvis march算法。你需要检查每个点实际上是凸包的一部分，你不能只延伸一次松紧带并做好它。
“有无论如何模拟橡皮筋在计算机中的效果”：不，不是计算复杂性。计算机操作一次处理的操作数不变。例如，典型的凸包算法将三点乘三点并检查它们是否形成顺时针或逆时针三角形。据说这是在不断的时间内完成的。
发布频带涉及所有N个点，不能实现为原始操作。
如果您尝试用计算机以某种方式模拟它，您可以确定它至少需要O（N日志（N））操作。无论如何，在一个离散的宇宙（整数坐标）中，O（N）可以使用基数排序。
有点不清楚橡皮筋的属性如何在算法上表现出来。机器人如何找到凸包多边形的顶点？通过观察多边形线的方向改变？ – Codor 2015-02-23 10:03:27
所以你不是在说这里的机器人算法（它是一个机器人是无关紧要的，如果我知道它的事实吗？），而是关于利用橡皮筋创造“免费”船体的事实？不，这一步*是实际算法，如果没有任何计算工作，就无法得到这个结果。 – Groo 2015-02-23 10:21:32
但在这个例子中，橡皮筋不会做任何牺牲吗？ – kiyarash 2015-02-23 11:13:13