Affiliations: The University of Pedagogy, Ho Chi Minh City, Vietnam. trungnn@hcmup.edu.vn | Multimedia Lab, The University of Information Technology (UIT), Vietnam National University, Ho Chi Minh City (VNU-HCM), Vietnam. ducda@uit.edu.vn
Note: [] Address for correspondence: The University of Information Technology (UIT) Km 20, Hanoi Road, Thu Duc District, Ho Chi Minh City, Vietnam
Abstract: 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(N3), 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.
Keywords: colored points, Voronoi diagram, min-max problem
