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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA17-05534S" target="_blank" >GA17-05534S: Meshless methods for large scattered spatio-temporal vector data visualization</a><br>

Continuities

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

Publication year

2019

Confidentiality

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

Article name in the collection

Computational Science and Its Applications – ICCSA 2019

ISBN

978-3-030-24288-6

ISSN

0302-9743

e-ISSN

—

Number of pages

14

Pages from-to

367-380

Publisher name

Springer

Place of publication

Cham

Event location

Saint Petersburg University, Saint Petersburg

Event date

Jul 1, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—