@InProceedings {felkel98sccg, UPDATE = { 2003-12-12 }, author = { Felkel Petr and Obdr{\v z}{\' a}lek, {\v S}t{\v e}p{\' a}n }, title = { Straight Skeleton Implementation }, year = { 1998 }, booktitle = { SCCG 98: Proceedings of the 14th Spring Conference on Computer Graphics }, pages = { 210--218 }, editor = { L{\'{a}}szl{\'{o}} Szirmay Kalos }, publisher = { Comenius University. Bratislava }, month = { 6 }, day = { 23--25 }, venue = { Budmerice, Slovakia }, isbn = { 80--223--0837--4 }, annote = { Straight skeleton (Angular Bisector Network, ABN) of a planar polygon, which can be grasped as a modification of a planar Voronoi diagram without parabolic arcs, has been successfully used by Oliva et al. as a part of a system for three dimensional reconstruction of objects from a given set of 2D contours in parallel cross sections. The algorithm itself is used for the construction of intermediate contour layers during the reconstruction process, in order not to create self intersected surface triangles or a surface with holes. But -- Oliva's algorithm is not publicly available and we have not found any other useful code on the net. We have followed our older ideas [4] and implemented our version of straight skeleton. Our algorithm runs in O ( nm + n log n ) time, where n denotes the total number of polygon vertices and m the number of reflex ones. }, authorship = { 50-50 }, psurl = { Felkel.ps.gz [compressed postscript, 146 kB] }, }