Geodesic
Skeletonization of a multiply-connected polygonal domain based on its boundary adjacent tree
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 9 (2006) no. 3, pp. 299-314 
L. M. Mestetskiy. Skeletonization of a multiply-connected polygonal domain based on its boundary adjacent tree. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 9 (2006) no. 3, pp. 299-314. http://geodesic.mathdoc.fr/item/SJVM_2006_9_3_a8/
@article{SJVM_2006_9_3_a8,
     author = {L. M. Mestetskiy},
     title = {Skeletonization of a~multiply-connected polygonal domain based on its boundary adjacent tree},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {299--314},
     year = {2006},
     volume = {9},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2006_9_3_a8/}
}
TY  - JOUR
AU  - L. M. Mestetskiy
TI  - Skeletonization of a multiply-connected polygonal domain based on its boundary adjacent tree
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2006
SP  - 299
EP  - 314
VL  - 9
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SJVM_2006_9_3_a8/
LA  - ru
ID  - SJVM_2006_9_3_a8
ER  - 
%0 Journal Article
%A L. M. Mestetskiy
%T Skeletonization of a multiply-connected polygonal domain based on its boundary adjacent tree
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2006
%P 299-314
%V 9
%N 3
%U http://geodesic.mathdoc.fr/item/SJVM_2006_9_3_a8/
%G ru
%F SJVM_2006_9_3_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of a continuous skeleton construction for a multiply connected polygonal domain is considered. The polygonal domain is a closed one, whose boundary consists of a finite number of simple polygons. The $O(n\log n)$ – algorithm for the worse case is offered, where $n$ is the number of polygonal domain vertices. The proposed algorithm creates the dual graph for the Voronoi diagram of the domain boundary. The solution is based on the adjacent tree of all the boundary polygons created by a sweepline method. In this case, sites and polygons are called adjacent if they have a common contact empty circle. The offered approach generalizes the Lee skeleton algorithm from a simple polygon to that with holes with the same running time.

[1] Mestetskii L. M., Nepreryvnyi skelet binarnogo rastrovogo izobrazheniya, Tr. Mezhdunar. konf. “Grafikon-98”, Moskva, 1998

[2] Kirkpatrick D. G., “Efficient computation of continuous skeletons”, Proc. of the 20th Annual IEEE Symposium on FOCS, 1979, 18–27

[3] Fortune S., “A sweepline algorithm for Voronoi diagrams”, Algorithmica, 2 (1987), 153–174 | DOI | MR | Zbl

[4] Yap C. K., “An $O(n\log n)$ algorithm for the Voronoi diagram of the set of simple curve segments”, Discrete Comput. Geom., 2 (1987), 365–393 | DOI | MR | Zbl

[5] Lee D. T., “Medial axes transform of planar shape”, IEEE Trans. Patt. Anal. Mach. Intell., 4 (1982), 363–369 | DOI | Zbl

[6] Mestetskii L. M., “Skeletizatsiya mnogougolnoi figury na osnove obobschennoi triangulyatsii Delone”, Programmirovanie, 3 (1999), 16–31 | MR

[7] Lagno D., Sobolev A., Modifitsirovannye algoritmy Forchuna i Li skeletizatsii mnogougolnoi figury, Tr. mezhdunar. konf. “Grafikon-2001”, Moskva, 2001

[8] Srinivasan V., Nackman L. R., Tang J.-M., Meshkat S. N., “Automatic mesh generation using the symmetric axis transform of polygonal domains”, Proc. of the IEEE 80, 9 (1992), 1485–1501 | DOI

[9] Lee D. T., Schachter B. J., “Two algorithms for constructing a Delaunay triangulation”, Int. J. Comput. Inf. Sci., 9 (1980), 219–242 | DOI | MR | Zbl

[10] Preparata F., Sheimos M., Vychislitelnaya geometriya: vvedenie, Mir, M., 1989 | MR | Zbl

[11] Dehne F., Klein R., ““The big sweep”: On the power of the wavefront approach to Voronoi Diagrams”, Algorithmica, 17 (1997), 19–32 | DOI | MR | Zbl

[12] Akho A., Khopkroft Dzh., Ulman Dzh., Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR