Optimization heuristics for computing the voronoi skeleton

D. Kotsur, V. Tereshchenko. Optimization heuristics for computing the voronoi skeleton. volume 11536, pages 96-111, DOI https://doi.org/10.1007/978-3-030-22734-0_8, 6, 2019.

Autoren
  • Dmytro Kotsur
  • Vasyl Tereshchenko
Editoren
  • J. Rodrigues
  • et al.
BuchComputational Science – Proc. ICCS 2019, Part I
TypIn Konferenzband
VerlagSpringer
SerieLecture Notes in Computer Science
Band11536
DOIhttps://doi.org/10.1007/978-3-030-22734-0_8
ISBN978-3-030-22733-3
Monat6
Jahr2019
Seiten96-111
Abstract

A skeletal representation of geometrical objects is widely used in computer graphics, computer vision, image processing, and pattern recognition. Therefore, efficient algorithms for computing planar skeletons are of high relevance. In this paper, we focus on the algorithm for computing the Voronoi skeleton of a planar object represented by a set of polygons. The complexity of the considered algorithm is O(N log N), where N is the total number of polygon’s vertices. In order to improve the performance of the skeletonization algorithm, we proposed theoretically justified shape optimization heuristics, which are based on polygon simplification algorithms. We evaluated the efficiency of such heuristics using polygons extracted from MPEG 7 CE-Shape-1 dataset and measured the execution time of the skeletonization algorithm, computational overheads related to the introduced heuristics and the influence of the heuristic onto the accuracy of the resulting skeleton. As a result, we established the criteria allowing us to choose the optimal heuristics for Voronoi skeleton construction algorithm depending on the critical system’s requirements.