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

fYear

2012

fDate

Feb. 27 2012-March 1 2012

Firstpage

1

Lastpage

4

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/rivf.2012.6169857

Filename

6169857