PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Identyfikatory
Warianty tytułu
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
Wydawca
Rocznik
Strony
219--229
Opis fizyczny
Bibliogr. 5 poz., rys., tab.
Twórcy
autor
  • The University of Pedagogy, Ho Chi Minh City, Vietnam
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-969066da-93f0-4ea9-bc4a-688bea6fbf39
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.