算法 - 寻找最大周长的三角形

Question

5

我被赋予一个由N个点组成的二维平面坐标(x,y)表示的集合。有没有一种快速算法可以选择三个点，使得这些点形成的三角形周长最大？

- David

1

暴力破解是唯一的方法。因此时间复杂度为 O(n^3)。 - nice_dev

2

实际上，在暴力算法中要检查的三角形数量将是（n 选 3），即 ~（n ^ 3）/6，因此复杂度确实为 O(n^3)。您可以忽略不属于凸包的点和位于直线上的点，但在最坏情况下仍然有 n 个点。 - m69 ''snarky and unwelcoming''

@Richardissimo 这个最大面积的解决方案是否也适用于最大周长？（将abc改进为abd意味着对于面积，d在通过c与ab平行的线之外，并且对于周长，d在以a和b为焦点的椭圆之外。） - m69 ''snarky and unwelcoming''

啊，抱歉，我的错误。最大周长并不意味着最大面积。（撤回重复建议。） - Richardissimo

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Declan Nnadozie · Answer 1

这是具有抢占性质的

检查是否可以构成三角形？如果不行，请在另一个轴上选择另一个最高点。

- גלעד ברקן · Answer 2

这是一个大致的想法（我对计算几何不太熟悉）。具有固定周长和底边的三角形可以生成一个椭圆。例如，在这里，B和C是固定的，任何点A在椭圆上将保持三角形周长相同：

对于连接两点的每个线段，从我们的集合中选择一个随机的第三个点。生成相应的椭圆，然后从我们的集合中选择另一个在该椭圆外的随机点。每个椭圆将排除生成周长相同或更小的三角形的点，直到我们用完所有点，找到最大的那个。当然，我们需要一些有效的方法来找到相关的点（也许使用空间划分？）。