定的点的集合，发现如果任意三个点的共线 [英] Given a set of points, find if any of the three points are collinear

问题描述

什么是最好的算法，以查找是否存在三点共线的点集说ñ。还请解释的复杂性，如果它是不平凡的。

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硬以及是否有子二次算法（即比O代表更好（N ^ 2））是一个开放的问题。许多常见的计算几何的问题（包括你）已经被证明是3SUM努力，这类问题越来越大。像NP-硬度，3SUM硬度的概念，证明了一些问题，韧性已被证明是有用的。

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纸：<一href="http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf">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点-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屋！