3622
правки
Изменения
→Wavefront-алгоритм
== Wavefront-алгоритм ==
Существует простой в понимании и реализации алгоритм для построения <tex> \mathrm{straigt}\ \mathrm{skeleton}</tex> на основе триангуляции, который работает за время <tex> O(n^3 \log n)</tex><ref>[http://resourceswww.mpi-inf.mpgsthu.deorg/departmentsresearch/d1publications/teachingfiles/ss10/Seminar_CGGC/Slides/09_Dinu_SSkeeurocg2010-slides.pdf Eric BerberichStefan Huber, Martin Held, "Straight Skeleton, Computational Geometry Skeletons and Geometric Computing Seminartheir Relation to Triangulations"]</ref>
Рассмотрим оригинальный алгоритм, который был предложен авторами этой структуры.