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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F19%3A43955680" target="_blank" >RIV/49777513:23520/19:43955680 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-030-24289-3_27" target="_blank" >http://dx.doi.org/10.1007/978-3-030-24289-3_27</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-24289-3_27" target="_blank" >10.1007/978-3-030-24289-3_27</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-05534S" target="_blank" >GA17-05534S: Meshless metody pro vizualizaci velkých časově-prostorových vektorových dat</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Computational Science and Its Applications – ICCSA 2019

ISBN

978-3-030-24288-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

367-380

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Saint Petersburg University, Saint Petersburg

Datum konání akce

1. 7. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—