Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
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