给定一组在平面上具有坐标的点，找到最大周长的简单多边形

Question

多边形必须由所有 n 个点组成。保证任意三个点不共线。现在，我只能想出蛮力算法。我想知道是否有另一种方法可以解决这个问题。点集的体积可以大到 10^5。 欢迎任何想法:)

Answer 1

这个问题看起来像是旅行商问题的一个版本。基本上，如果你有一组 N 个平面点 p1, p2, ..., pN，你可以认为它们形成了一个图的顶点，并且在它们中的任意两个 pi pj 之间有一条边（解释为一条直线段）连接两点，所以它是N个点的全连通图（组合上相当于N维辛）。此外，可以在该图的每条边上分配一个权重，权重是它连接的两点之间的距离（即连接两点的直线段的长度）。现在，目标是找到一条哈密顿循环路径，使其包含的边上的权重总和最大化。除此之外，还有一个进一步的限制，即循环路径必须是一个简单的平面循环，所以你必须放弃任何你得到的自相交的解决方案。

我认为这是一个棘手的问题，所以也许可以从维基百科开始：The Longest Path Problem and The Travelling Salesman Problem 并检查那里提到的一些精确的、启发式的和近似的算法。