是否有一种已知的、有效的算法来找到云中最接近的三个点组?
这类似于最近点对问题，但我要寻找三个点，而不是两个。
编辑
"最接近"的定义会影响算法的复杂度。正如Jack指出的那样，找到最小面积三角形是一件非常困难的事情，无论如何都不适合我的应用。
我希望有一个更有效的算法来找到最小周长(即|AB|+|AC|+|BC|)三角形或类似的东西(例如最小|AB|²+|AC|²+|BC|²)。我不知道为什么这应该是3和难的，因为其他地方存在3个共线点不会影响结果。
注意:我的点有八个维度，所以任何限制维度更少的算法都不适合。
这个问题类似于在一组点中寻找最近的对的经典问题。你可以采用最坏情况O(n log n)算法来解决最接近对问题。
这个具体的问题出现在Google的Code Jam竞赛中。以下是分析的简历:
进一步:点的数量可能非常大，所以我们需要一个有效的算法。我们可以用分治法在O(n log n)时间内解决这个问题。我们将用一条垂直线将点集合分成两个大小相等的集合。对于最小周长三角形，现在有三种情况:它的三个点可以完全在左集合，也可以完全在右集合，或者它可以使用每一半的点。
"求第三种情况的最小周长(如果小于p)":
- 选取距离垂直分隔线p/2范围内的点。 然后我们从上到下遍历这些点，并维护一个大小为p x p/2的盒子中所有点的列表，盒子的底部边缘位于最近考虑的点。
- 当我们将每个点添加到盒子中时，我们使用该点和盒子中的每对点计算所有三角形的周长。(我们可以完全排除分界线左侧或右侧的三角形，因为这些已经被考虑过了。)
我们可以证明盒子里的点最多有16个，所以每个点最多只需要考虑一个小的常数个数的三角形。
在我看来，你甚至可以调整这种方法，使其适用于|AB|²+|AC|²+|BC|²的情况。
在O(n^2)中有一个明显的算法。
1)进行Delaunay三角剖分- O(n log n)，得到一个平面图形。
因为是Delaunay三角化，最大化最小角度，很明显，最近的3个点必须由至少2条边连接(但它们不一定需要形成三角形!)否则会有更多更近的点或更封闭的角。
2)对于每个点(图的顶点)，我们检查每一对相邻的边，并查看由这2条边定义的3个顶点。
步骤2)要花多少时间?由于图是平面的，所以边数为<= 3n - 6，即O(n)。所以这一步在最坏的情况下将使用O(n^2)(在典型情况下使用O(n)，其中每个顶点的度数是有限的)。
所以整个算法是O(n^2)。请注意，步骤2)在某种程度上是幼稚的(蛮力)解决方案，所以我认为还有改进的空间(此外，步骤1和步骤2可能会以某种方式合并)。
这是k最近邻问题的一种特殊形式，即k=3。引用的页面没有说明算法的复杂性，但很明显可以看到，计算从选定点到所有其他点的距离，然后计算从该点到所有其他点的距离以及从原始点到新选定点的距离的朴素方法是O(nk-1)。考虑以下伪代码:
for pointB in searchSpace do:
distanceAB := calculateDistance(pointA, pointB)
for pointC in {searchSpace} - {pointB} do:
distanceBC := calculateDistance(pointB, pointC)
distanceCA := calculateDistance(pointC, pointA)
if (distanceAB + distanceBC + distanceCA) < currentMin then:
currentMin := distanceAB + distanceBC + distanceCA
closestPoints := {pointA, pointB, pointC}
注意，我们假设pointA已经从searchSpace中移除。这是一个O(n2)算法。假设维数相对较小，或者函数calculateDistance随维数线性增长或更小，这将在适当的时间限制下给出解决方案。当然可以进行优化，但可能不是必需的。
如果你想看一些真实的代码，维基百科有很多实现的链接。
你提到的问题是3和的变型难题。详情请浏览http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf。
这个问题也可以表示为从给定的点求最小的三角形。
编辑:本质上，3和难题意味着下界是O(n^2)。这里那里可能会有一些小的改进，但没有什么可以做的。
对于这个特定的问题(最小三角形)，请参见http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf的第3章。
Thomas Ahle的答案很好地解释了逻辑，但是它没有相同的代码。
下面是相同
的Java实现import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class MainClass {
static class Point{
double x;
double y;
Point(double x, double y){
this.x = x;
this.y =y;
}
}
static class ComparatorByXCoordinate implements Comparator<Point>{
@Override
public int compare(Point P1, Point P2) {
if (P1.x > P2.x) return 1;
if (P1.x < P2.x) return -1;
return Double.compare(P1.y, P2.y);
}
}
static class ComparatorByYCoordinate implements Comparator<Point>{
@Override
public int compare(Point P1, Point P2) {
return Double.compare(P1.y, P2.y);
}
}
static double DistanceBetweenPoints(Point P1, Point P2){
return Math.sqrt((P1.x-P2.x)*(P1.x-P2.x) + (P1.y-P2.y)*(P1.y-P2.y));
}
static double Perimeter(Point A, Point B, Point C){
return DistanceBetweenPoints(A, B) + DistanceBetweenPoints(B, C) + DistanceBetweenPoints(C, A);
}
public static void main(String[] args) throws IOException {
InputStreamReader r = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(r);
int n = Integer.parseInt(br.readLine());
Point[] PointsX = new Point[n];
Point[] PointsY = new Point[n];
for (int i = 0; i < n; i++){
String[] st = br.readLine().split(" ");
double xCoordinate = Double.parseDouble(st[0]);
double yCoordinate = Double.parseDouble(st[1]);
Point p = new Point(xCoordinate, yCoordinate);
PointsX[i] = p;
PointsY[i] = p;
}
Arrays.sort(PointsX, new ComparatorByXCoordinate());
Arrays.sort(PointsY, new ComparatorByYCoordinate());
System.out.printf("%.12f", solveNoCross(PointsX, PointsY, 0, n));
}
static double solveNoCross(Point[] PointsX, Point[] PointY, int low, int high){
if (high - low < 3){
return Double.MAX_VALUE;
}
else if (high - low == 3){
return Perimeter(PointsX[low], PointsX[low+1], PointsX[low+2]);
}
int mid = low + (high-low)/2; //Overflow Issues :(
Point midPoint = PointsX[mid];
Point[] firstHalf = new Point[mid - low];
Point[] secondHalf = new Point[high - mid];
int firstHalfPointer = 0;
int secondHalfPointer = 0;
for (Point point: PointY){
double pointX = point.x;
double pointY = point.y;
double midX = midPoint.x;
double midY = midPoint.y;
if (pointX < midX || (pointX == midX && pointY < midY)){
firstHalf[firstHalfPointer++] = point;
}
else{
secondHalf[secondHalfPointer++] = point;
}
}
double min = Math.min(solveNoCross(PointsX, firstHalf, low, mid),
solveNoCross(PointsX, secondHalf, mid, high));
return Math.min(min, solveCross(PointY, midPoint, min, PointY.length));
}
private static double solveCross(Point[] pointY, Point midPoint, double min, int pointYLen) {
// For Solving When There Are Cross Triangles Such That Some Vertices Are in One Half and Some in Other
double midX = midPoint.x;
double midY = midPoint.y;
double MCP = Double.MAX_VALUE; // Minimum Cross Perimeter
int boundingFactor = 0;
double periRange;
ArrayList<Point> pointsInPeriRange = new ArrayList<>();
if (min == Double.MAX_VALUE){
periRange = 2 * 1E9;
}
else{
periRange = min/2;
}
for (int FirstPointIterator = 0; FirstPointIterator < pointYLen; FirstPointIterator++){
Point Firstpoint = pointY[FirstPointIterator];
double FirstPointX = Firstpoint.x;
double FirstPointY = Firstpoint.y;
if(Math.abs(FirstPointX - midX) > periRange) continue;
while(boundingFactor < pointsInPeriRange.size() && FirstPointY - pointsInPeriRange.get(boundingFactor).y > periRange) {
boundingFactor += 1;
}
for (int SecondPointIterator = boundingFactor; SecondPointIterator < pointsInPeriRange.size(); SecondPointIterator++){
for (int ThirdPointIterator = SecondPointIterator + 1; ThirdPointIterator < pointsInPeriRange.size(); ThirdPointIterator++){
Point SecondPoint = pointsInPeriRange.get(SecondPointIterator);
Point ThirdPoint = pointsInPeriRange.get(ThirdPointIterator);
MCP = Math.min(MCP, Perimeter(Firstpoint, SecondPoint, ThirdPoint));
}
}
pointsInPeriRange.add(Firstpoint);
}
return MCP;
}
}
输入格式是一个整数，表示点的个数后面跟着点!
Sample Run -
输入:4
0 0
0 3
3 0
1 1
6.650281539873