Efficient Speed-Up of the Smallest Enclosing Circle Algorithm

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43965057" target="_blank" >RIV/49777513:23520/22:43965057 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.15388/22-INFOR477" target="_blank" >https://doi.org/10.15388/22-INFOR477</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.15388/22-INFOR477" target="_blank" >10.15388/22-INFOR477</a>

Result language

angličtina

Original language name

Efficient Speed-Up of the Smallest Enclosing Circle Algorithm

Original language description

The smallest enclosing circle is a well-known problem. In this paper, we propose modifications to speed-up the existing Weltzl’s algorithm. We perform the preprocessing to reduce as many input points as possible. The reduction step has lower computational complexity than the Weltzl’s algorithm and thus speed-ups its computation. Next, we propose some changes to Weltzl’s algorithm. In the end are summarized results, that show the speed-up for 10^6 input points up to 100 times compared to the original Weltzl’s algorithm. Even more, the proposed algorithm is capable to process significantly larger data sets than the standard Weltzl’s algorithm.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10102 - Applied mathematics

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

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

Name of the periodical

INFORMATICA

ISSN

0868-4952

e-ISSN

1822-8844

Volume of the periodical

33

Issue of the periodical within the volume

3

Country of publishing house

LT - LITHUANIA

Number of pages

11

Pages from-to

623-633

UT code for WoS article

000933656100008

EID of the result in the Scopus database

2-s2.0-85166160365