algorithm - 多边形构造的复杂性

Question

我想证明从给定的一组点（2D）构造一个简单多边形的问题的复杂性至少是O(n logn) ，即每个正确的算法至少需要 O(n logn) 步骤来解决这个问题最坏情况下的问题。是否有可能以某种方式将此问题简化为排序问题，或者如何显示？

Answer 1

是的，使用基线算法：

• 找到具有最低和最高 x 值的两个点：O(n)
• 将位于基线上方和下方的其他点分成两组（连接这些点的线）：O(n)
• 按“升序 y/升序 x”排序上集：O(n*logn)
• 按“降序 y/降序 x”排序较低的集合：O(n*logn)
• 按顺序加入上层集合，按顺序加入下层集合：O(n)

Answer 2

是的，可以通过将其与排序问题进行比较来证明它，但你必须反过来减少它。也就是说，在 O(n) 时间内将排序问题简化为多边形构造问题。