IVl*_*lad 4 algorithm optimization computational-geometry
给定一组n点,我们能找到三个点来描述最小面积的三角形O(n^2)吗？如果是,如何,如果没有,我们能做得更好O(n^3)吗？
我发现一些论文表明这个问题至少和要求找到三个共线点(一个面积为0的三角形)的问题一样困难.这些论文O(n^2)通过将其简化为三和问题的实例来描述该问题的解决方案.然而,我无法找到任何我感兴趣的解决方案.请参阅此(查找一般位置)以获取此类论文以及有关3-sum的更多信息.
小智 5
有用于找到最小面积三角形的O(n 2)算法.
例如,你可以在这里找到一个:http://www.cs.tufts.edu/comp/163/fall09/CG-lecture9-LA.pdf
如果我正确理解pdf,基本思路如下:
对于每对AB点,您可以找到最接近它的点.
你构造了一个双重点,以便行< - >指向.线y = mx + c映射到点(m,c)
在对偶中,对于给定点(对应于原始点集中的段),最近的线垂直给出了1所需的点.
显然2和3可以在O(n 2)时间内完成.
此外,我怀疑论文通过减少到 3SUM 来显示3SUM硬度.它应该是反过来的.