A Better Heuristic Algorithm for Finding the Closest Trio of 3-colored Points from a Given Set of 3-colored Points on a Plane

摘要

We consider the following problem: Given n red points, m green points and p blue points on a plane, find a trio of red-green-blue points such that the distance between them is smallest. This problem could be solved by an exhaustive search algorithm: test all trios of 3 different colored points and find the closest trio. However, this algorithm has the complexity of O(N~3), N = max(n,p, q). In our previous research, we already showed a heuristic algorithm with a good complexity to solve this problem based on 2D Voronoi diagram. In this paper, we introduce a better heuristic algorithm for solving this problem. This new heuristic algorithm has the same complexity but it performs much better than the old one.