Select the smallest distance by coordinates

Question

Algorithms

Tell me some algorithm that will select from an array of coordinates (x, y) three coordinates that form a triangle of the smallest perimeter.

PS In an array, the coordinates can match, and the triangle can be with zero area.

Answer 1

My God, accordion problem on algorithmic programming.
Split the points into two halves with the same number of points on the vertical line. We recursively found the answer for two halves - let such a minimum perimeter in two halves be equal to P.
It remains to disassemble the triangles that have one vertex in one half and two others in the second. It suffices for us to consider only points at a distance <= P / 2 from the line of division.
Now we go through the points in this strip from top to bottom, maintaining a set of points that are located vertically from ours at a distance of no more than P / 2. That is, we go through a kind of floating window of width P / 2 - we get two types of events - the point got inside the window and the dot came out of the window.
If there is no triangle inside the window that has a perimeter less than P, then in this window (offhand) there can be no more than 7 points (since the window is a rectangle P x ​​P / 2). These 7 points can already be sorted out for cubic complexity. Otherwise, there is necessarily a triangle with a perimeter less than P, which we will stumble upon. Each time, bumping into such a triangle, we will simply reduce P to a new value.
Thus, we have an algorithm with complexity satisfying the estimate T(n) = 2T(n / 2) + O(nlogn), whose solution is O(n*log^2(n))

Answer 2

An interesting task ... I will also wait for answers, because. nothing comes to mind other than a dumb rant...

Answer 3

You can calculate all distances (N ² and associate these distances with both points (2N memory), you can sort in ascending order.
Then go through all the points again and find for them two complementing them to a triangle with a minimum perimeter. Moreover, you can not check the points, which are farther than half of the already found minimum perimeter.If we sorted the distances during the association, then the search should end very
quickly.You can try to optimize, when associating with the points of the nearest distances, store only the minimum, let's say 3. Here we need to analyze how not to lose the true solution as a result of this optimization.

Answer 4

You can use some greedy algorithm instead of exhaustive search, always trying to find a triangle of minimum perimeter. There is such a profit here that having already a certain triangle, you can ignore all distances that are not less than half of its perimeter. I find it difficult to evaluate such an algorithm.

Answer 5

The more specific the task, the better it can be optimized.
For example, if it is known in advance that the points are evenly scattered on the plane (limited by a rectangle), and there are a lot of points at the same time (otherwise it is easier to enumerate), then the first thing that comes to mind is to divide the plane into zones. For example, there are about 10,000 points, and we divide the rectangle into a 10x10 chessboard. Each cell will contain approximately 100 points. Next, we calculate not the full set of options, but only neighboring cells. Those. it turns out not (10.000 * 9999 * 9998) / 2 options, but only (10.000 * 900 * 899) / 2. This is a rough example, but it shows that this optimization is not universal - two refinements were used here, i.e. the task is narrower.
In short, more specifics are needed.

Answer 6

points are set like this 3<N<=100000, and there is not enough time, so, alas, there is no way to enumerate.

Answer 7

yes forgot to add uniformity is not guaranteed. But the coordinates are limited to a rectangle, let's say from -1,000,000 to 1,000,000 in X and Y

Answer 8

the table will be 10^9 memory cells, it will take too long to fill it. I would like to find an algorithm that does not require enumeration of all distances between coordinates. Surely a similar problem has already been solved by mankind more than once. Can anyone recommend a book?

Answer 9

The previous answer is really good.
I got another idea. The solution is not ideal, but who knows, it can give good results ...
1) We order all points by distance from the origin (x ^ 2 + y ^ 2).
2) Then we go through the ordered array again, calculating the total distance between each three neighboring points in the array (the perimeter of the triangle). A triple with a minimum perimeter will give the required triangle.
Here, if I'm not mistaken, it generally turns out O (n).
Yes, sorting itself is not O(n), but slower. For optimization, you can initially make the array sorted, i.e. insert points into the desired element, it will speed up a little.
Of course, the method of definition is not exact (for sure, some triangles will be “eaten”, but since you need “quickly” - O (n) - perhaps a good option. What do you think?