Given an even number of vertices, how to find the optimal set of pairs based on proximity?

Question

Problem:

• We have many n vertices in three-dimensional Euclidean space, and there is an even number of these vertices.

• We want to connect them by their proximity. In other words, we would like to find a set of vertex pairs where the vertices in each pair will be as close to each other as possible.

• We want to minimize the possible loss of proximity between the vertices of any other pairs as much as possible.

• I'm not looking for the most optimal solution (even if it strictly exists / can be made), just a reasonable one, which can be calculated relatively quickly.

A relatively terrible brute force approach involves picking peaks and going through the rest to find the closest neighbor, and then repeat until there are none left. Of course, when we approach the end of the list, the nearest peak may be very far away, but this is the only choice, so it can get much worse in the third paragraph above.

Answer 1

A common approach for such problems (especially if n is large) is to pre-compile the spatial index structure like kd tree or octtree and search for nearest neighbors using this helps. Through the octtree nodes, the available point is placed in the bunkers, so you can be sure that they are mutually close. You also minimize the number of comparisons.

Implementation sketch with an octet: you need a Node class that stores its bounding box. The resulting LeafNode class stores a small number of points to the maximum (for example, k = 20), which are added using the insert function. The derived NonLeafNode class stores links to 8 subnods (which can be either Leaf or NonLeafNodes).

The tree is represented by the root of the node, all insertions and queries begin here. The tree is created starting from the first k points inserted in the LeafNode. If k + 1st point is inserted, the bounding box is divided into 8 sub-boxes, and the points contained in it are sorted. The current LeafNode is replaced with one NonLeafNode with 8 subnodes. This is repeated until all points are in the tree.

To find the nearest neighbor, the tree moves, starting with the root Node, comparing it with the bounding box. If the request point is in the Node bounding box, the crawl is in node. Please note: if you find the nearest candidate, you also need to check with neighboring nodes in the octet.

To verify the implementation of kdtree, the wikipedia page looks rather complicated.

Answer 2

Since you are not looking for the optimal solution, here you can consider heuristics.

For each p, calculate two points: the nearest neighbor and the farthest neighbor, the nearest and farthest to p, respectively. Now let q be the point with the largest distant neighbor (q is the extreme point at the entrance). Match q to your nearest neighbor, remove both of them and recursively calculate the correspondence for the remaining points.

This, of course, is NOT optimal, but it works really well on small input sets. If you need an optimal solution, you should read about the Euclidean matching problem .