Title :
A Heuristic Algorithm for Finding the Closest Trio of 3-Colored Points from a Given Set of 3-Colored Points on Plane
Author :
Nguyen, Trung N. ; Duong, Duc A.
Author_Institution :
Dept. of Comput. Sci., HCMC Univ. of Pedagogy, Ho Chi Minh City, Vietnam
fDate :
Feb. 27 2012-March 1 2012
Abstract :
The problem considering in this paper is as follows: Given n red points, m green points and p blue points on plane, how to 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 one. However, this algorithm has a big complexity: O(nmp). In this paper, we will present a heuristic algorithm with a better complexity to solve this problem. The heuristic algorithm is based on 2D Voronoi diagram.
Keywords :
computational complexity; computational geometry; search problems; 2D Voronoi diagram; 3-colored points; closest trio; complexity; exhaustive search algorithm; heuristic algorithm; plane; red-green-blue points; Algorithm design and analysis; Complexity theory; Computer science; Data structures; Educational institutions; Heuristic algorithms; Search problems;
Conference_Titel :
Computing and Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), 2012 IEEE RIVF International Conference on
Conference_Location :
Ho Chi Minh City
Print_ISBN :
978-1-4673-0307-1
DOI :
10.1109/rivf.2012.6169857
