给定一组点，找出三个点中是否有任何一个共线 [英] 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.

谢谢
巴拉

推荐答案

如果你能想出比 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屋！