Přejít k obsahu


Fast Algorithm for Finding Maximum Distance with Space Subdivision in E2

Citace:
SKALA, V., MAJDIŠOVÁ, Z. Fast Algorithm for Finding Maximum Distance with Space Subdivision in E2. In 8th International Conference, ICIG 2015, Tianjin, China, August 13-16, 2015, Proceedings, Part II. Cham: Springer, 2015. s. 261-274. ISBN: 978-3-319-21962-2 , ISSN: 0302-9743
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Fast Algorithm for Finding Maximum Distance with Space Subdivision in E2
Rok vydání: 2015
Místo konání: Cham
Název zdroje: Springer
Autoři: Prof. Ing. Václav Skala CSc. , Ing. Zuzana Majdišová
Abstrakt CZ: Nalezení přesné maximální vzdálenosti dvou bodů v dané množině dat je základní výpočetní problém, který je řešen v mnoha aplikacích. Tento článek popisuje rychlý, implementačně jednoduchý a robustní algoritmus pro nalezení maximální vzdálenosti dvou bodů v E2. Popsaný algoritmus využívá polárního dělení, po kterém následuje rozdělení zbývajících bodů do uniformní mřížky. Hlavní myšlenka tohoto algoritmu spočívá v eliminaci co nejvíce bodů předtím, než je přistoupeno k hledání maximální vzdálenosti. Navržený algoritmus poskytuje v porovnání se standardním algoritmem významné urychlení.
Abstrakt EN: Finding an exact maximum distance of two points in the given set is a fundamental computational problem which is solved in many applications. This paper presents a fast, simple to implement and robust algorithm for finding this maximum distance of two points in E2. This algorithm is based on a polar subdivision followed by division of remaining points into uniform grid. The main idea of the algorithm is to eliminate as many input points as possible before finding the maximum distance. The proposed algorithm gives the significant speed up compared to the standard algorithm.
Klíčová slova

Zpět

Patička