1. Home
  2. Issues
  3. Volume 33, Issue 3 (2022)
  4. Efficient Speed-Up of the Smallest Enclo ...

Informatica


Efficient Speed-Up of the Smallest Enclosing Circle Algorithm
Volume 33, Issue 3 (2022), pp. 623–633
Pub. online: 18 March 2022      Type: Research Article      Open accessOpen Access
Received
1 February 2021
Accepted
1 February 2022
Published
18 March 2022

Abstract

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.

References

 
Efrat, A., Sharir, M., Ziv, A. (1993). Computing the smallest k-enclosing circle and related problems. In: Workshop on Algorithms and Data Structures. Springer, pp. 325–336.
 
Efrat, A., Sharir, M., Ziv, A. (1994). Computing the smallest k-enclosing circle and related problems. Computational Geometry, 4(3), 119–136.
 
Gao, S., Wang, C. (2018). A new algorithm for the smallest enclosing circle. In: 2018 8th International Conference on Management, Education and Information (MEICI 2018), Atlantis Press.
 
Har-Peled, S., Mazumdar, S. (2003). Fast algorithms for computing the smallest k-enclosing disc. In: European Symposium on Algorithms. Springer, pp. 278–288.
 
Har-Peled, S., Mazumdar, S. (2005). Fast algorithms for computing the smallest k-enclosing circle. Algorithmica, 41(3), 147–157.
 
Megiddo, N. (1983). Linear-time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing, 12(4), 759–776.
 
Skala, V. (2013). Fast Oexpected(N) algorithm for finding exact maximum distance in E2 instead of O(N2) or O(Nlog N). In: AIP Conference Proceedings, Vol. 1558. American Institute of Physics, pp. 2496–2499.
 
Skala, V., Majdisova, Z. (2015). Fast algorithm for finding maximum distance with space subdivision in E2. In: International Conference on Image and Graphics. Springer, pp. 261–274.
 
Skala, V., Smolik, M. (2015). A point in non-convex polygon location problem using the polar space subdivision in E2. In: International Conference on Image and Graphics. Springer, pp. 394–404.
 
Skala, V., Majdisova, Z., Smolik, M. (2016a). Space subdivision to speed-up convex hull construction in E3. Advances in Engineering Software, 91, 12–22.
 
Skala, V., Smolik, M., Majdisova, Z. (2016b). Reducing the number of points on the convex hull calculation using the polar space subdivision in E2. In: 2016 29th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI). IEEE, pp. 40–47.
 
Skyum, S. (1991). A simple algorithm for computing the smallest enclosing circle. Information Processing Letters, 37(3), 121–125.
 
Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids). In: Maurer, H. (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Vol. 555. Springer, Berlin, Heidelberg.
 
Xu, S., Freund, R.M., Sun, J. (2003). Solution methodologies for the smallest enclosing circle problem. Computational Optimization and Applications, 25(1–3), 283–292.

Biographies

Smolik Michal
smolik@kiv.zcu.cz

M. Smolik received the PhD degree in software engineering from the University of West Bohemia, Czech Republic, in 2020. He currently holds the position of researcher at the Department of Computer Graphics at the University of West Bohemia. His research areas are meshless methods for approximation and interpolation, specifically Radial basis functions. He works in the area of vector fields and develops basic algorithms connected with computer graphics.

Skala Vaclav
skala@kiv.zcu.cz

V. Skala is a full professor of computer science at the University of West Bohemia, Plzen, Czech Republic. He received his ING. (equivalent of MSc) degree in 1975 from the Institute of Technology in Plzen and CSc. (equivalent of PhD) degree from the Czech Technical University in Prague, in 1981. In 1996, he became a full professor in computer science. His current research interests are computer graphics and visualization, applied mathematics, especially geometrical algebra, algorithms, and data structures.


Full article Cited by PDF XML
Full article Cited by PDF XML

Copyright
© 2022 Vilnius University
Open access article under the CC BY license.

Keywords
smallest enclosing circle space subdivision convex hull speed-up Weltzl’s algorithm

Funding
The research was supported by the University of West Bohemia – Institutional research support No. 1311, and by SGS 2019-016.

Metrics
since January 2020
843

Article info
views

 765

Full article
views
566

PDF
downloads

 152

XML
downloads


Share


RSS