我想证明，在给定的一组点（2D）中构造一个简单多边形的问题的复杂性至少是O（nLogn），即在最坏的情况下，每个正确的算法至少需要O（nLogn）步骤来解决这个问题。
是否有可能以某种方式将此问题简化为排序问题，或者如何显示此问题？
最佳答案
是，使用基线算法：
找到x值最低和最高的两点：O（n）
将位于基线上下的其他点分成两组（连接这些点的直线）：o（n）
在“升序y/升序x”中对上集排序-顺序：o（n*logn）
按“降序y/desending x”排序下集-顺序：o（n*logn）
按顺序联接上集，按顺序联接下集：O（n）