我想证明从给定的一组点 (2D) 构造一个简单多边形 的问题的复杂性至少是 O(nlogn) ，即每个正确的算法在最坏的情况下至少需要 O(nlogn) 步来解决这个问题。 是否有可能以某种方式将此问题简化为排序问题或如何显示？
最佳答案
是的，使用基线算法:
- 找到 x 值最低和最高的两个点:O(n)
- 将位于基线上方和下方的两组中的其他点分开(连接这些点的线):O(n)
- 按“y 升序/x 升序”顺序对上部集合进行排序:O(n*logn)
- 按“y 降序/x 降序”顺序对较低的集合进行排序:O(n*logn)
- 按顺序加入上层集合，按顺序加入下层集合:O(n)
关于algorithm - 多边形构造的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17132308/