给出一组点，找出三点是否共线 [英] Given a set of points, find if any of the three points are collinear

问题描述

如果在一组点n中有任何三个点是共线的，那么最好的算法是什么？请同时解释复杂性，如果不是微不足道的话。

What is the best algorithm to find if any three points are collinear in a set of points say n. Please also explain the complexity if it is not trivial.

感谢

Bala

Thanks
Bala

推荐答案

如果你可以想出比O（N ^ 2）更好的算法，你可以发布它！

If you can come up with a better than O(N^2) algorithm, you can publish it!

这个问题是 3-SUM Hard ，以及是否存在亚二次算法（即比O（N ^ 2）好）是一个开放的问题。许多常见的计算几何问题（包括您的）已被证明是3SUM难，而且这类问题正在增长。像NP-Hardness一样，3SUM-Hardness的概念已被证明在证明某些问题的韧性方面是有用的。

This problem is 3-SUM Hard, and whether there is a sub-quadratic algorithm (i.e. better than O(N^2)) for it is an open problem. Many common computational geometry problems (including yours) have been shown to be 3SUM hard and this class of problems is growing. Like NP-Hardness, the concept of 3SUM-Hardness has proven useful in proving 'toughness' of some problems.

为了证明您的问题是3SUM，请参考这里的优秀的surver论文： http://www.cs.mcgill.ca/ 〜jking / papers / 3sumhard.pdf

For a proof that your problem is 3SUM hard, refer to the excellent surver paper here: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf

上述文章中您的问题出现在第3页（方便地称为3-POINTS-ON-LINE）。

Your problem appears on page 3 (conveniently called 3-POINTS-ON-LINE) in the above mentioned paper.

所以，目前最知名的算法是O（N ^ 2），你已经有了： - ）

So, the currently best known algorithm is O(N^2) and you already have it :-)

这篇关于给出一组点，找出三点是否共线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！