Přejít k obsahu


Simple and Fast Oexp(N) Algorithm for Finding an Exact Maximum Distance in E2 Instead of O(N^2) or O(N lgN)

Citace:
SKALA, V., ŠMOLÍK, M. Simple and Fast Oexp(N) Algorithm for Finding an Exact Maximum Distance in E2 Instead of O(N^2) or O(N lgN). In Computational Science and Its Applications – ICCSA 2019. Cham: Springer, 2019. s. 367-380. ISBN: 978-3-030-24288-6 , ISSN: 0302-9743
Druh: STAŤ VE SBORNÍKU
Jazyk publikace: eng
Anglický název: Simple and Fast Oexp(N) Algorithm for Finding an Exact Maximum Distance in E2 Instead of O(N^2) or O(N lgN)
Rok vydání: 2019
Místo konání: Cham
Název zdroje: Springer
Autoři: prof. Ing. Václav Skala CSc. , Ing. Michal Šmolík
Abstrakt CZ: Jedním z nich je nalezení maximální vzdálenosti bodů v E2 nebo v E3. Je to častý úkol vyžadovaný v mnoha aplikacích. Navzdory skutečnosti, že se jedná o extrémně jednoduchý úkol, je známým algoritmem „Brute force“ složitost O (N2). Vzhledem k této složitosti je doba chodu velmi dlouhá a nepřijatelná, zejména pokud mají být zpracovávány střední nebo větší datové sady. Alternativní přístup je konvexní výpočet trupu s komplexností vyšší než O (N) následovaný výpočtem průměru s komplexností O (M2). Situace je podobná třídění, kde algoritmus třídění bublin má složitost O (N2), kterou nelze v praxi použít ani pro střední datové sady. Tento článek popisuje nový a rychlý, jednoduchý a robustní algoritmus s O (N) očekávanou složitostí, který umožňuje zkrátit dobu potřebnou k nalezení maximální vzdálenosti dvou bodů v E2. Lze ho snadno upravit pro případ Ek obecně. Navržený algoritmus byl experimentálně vyhodnocen na větších souborech dat za účelem ověření a prokázání jeho očekávaných vlastností. Experimenty prokázaly výhody navrhovaného algoritmu oproti standardním algoritmům založeným na přístupech „Brute force“, konvexního trupu nebo konvexního trupu. Navrhovaný algoritmus poskytuje výrazné zrychlení aplikací, když jsou zpracovávány střední a velké datové sady. Je více než 10 000 krát rychlejší než standardní algoritmus „Brute force“ pro 106 bodů náhodně rozložených bodů v E2 a více než 4krát rychlejší než výpočet konvexního průměru trupu. Zrychlení navrhovaného algoritmu roste s počtem zpracovaných bodů.
Abstrakt EN: Finding a maximum distance of points in E2 or in E3 is one of those. It is a frequent task required in many applications. In spite of the fact that it is an extremely simple task, the known “Brute force” algorithm is of O(N2) complexity. Due to this complexity the run-time is very long and unacceptable especially if medium or larger data sets are to be processed. An alternative approach is convex hull computation with complexity higher than O(N) followed by diameter computation with O(M2) complexity. The situation is similar to sorting, where the bubble sort algorithm has O(N2) complexity that cannot be used in practice even for medium data sets. This paper describes a novel and fast, simple and robust algorithm with O(N) expected complexity which enables to decrease run-time needed to find the maximum distance of two points in E2. It can be easily modified for the Ek case in general. The proposed algorithm has been evaluated experimentally on larger different datasets in order to verify it and prove expected properties of it. Experiments proved the advantages of the proposed algorithm over the standard algorithms based on the “Brute force”, convex hull or convex hull diameters approaches. The proposed algorithm gives a significant speed-up to applications, when medium and large data sets are processed. It is over 10 000 times faster than the standard “Brute force” algorithm for 106 points randomly distributed points in E2 and over 4 times faster than convex hull diameter computation. The speed-up of the proposed algorithm grows with the number of points processed.
Klíčová slova

Zpět

Patička