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

• Autorzy: Nguyen N. T. , Duong A. D.

Identyfikatory

DOI

10.3233/FI-2014-989

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

colored points; Voronoi diagram; minmax problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 2
• Strony: 219--229
• Opis fizyczny: Bibliogr. 5 poz., rys., tab.

Twórcy

autor

Nguyen N. T.

• The University of Pedagogy, Ho Chi Minh City, Vietnam

autor

Duong A. D.

• Multimedia Lab, The University of Information Technology (UIT), Vietnam National University, Ho Chi Minh City (VNU-HCM), Vietnam

Bibliografia

• [1] Ngoc-Trung N., Anh-Duc D.: A heuristic algorithm for finding the closest trio of 3 colored points from a given set of 3 colored points on plane, Proceding of the 9th IEEE-RIVF International Conference on Computing and Comunication Technologies, 2012, p. 253–256.
• [2] Ngoc-Trung N., Thi-Dieu-Huyen T.: An algorithm for finding the closest pair of 2 colored points from a set of 2 colored points on plane, Journal of Natural Sciences, Hochiminh University of Pedagogy, No.10, 2008, p. 14–24.
• [3] De-Berg M., Van-Krefeld M., Overmars M., Schwarzkopf O.: Computational Geometry Algorithms and Applications, Springer, 1998.
• [4] Aurenhammer F.: Voronoi Diagrams: A survey of a fundamental geometric data structure, ACM Computing Surveys, No.23, 1991.
• [5] Shamos M., Hoey D,: Closest point problem, In proc, 16 Annu. IEEE Sympos, Found. Comput. Sci., , 1975, p. 151–162.