\input zb-basic
\input zb-ioport
\iteman{io-port 01292414}
\itemau{Chin, F.; Snoeyink, J.; Wang, C.A.}
\itemti{Finding the medial axis of a simple polygon in linear time.}
\itemso{Discrete Comput. Geom. 21, No.3, 405-420 (1999).}
\itemab
Summary: We give a linear-time algorithm for computing the medial axis of a simple polygon $P$. This answers a long-standing open question -- previously, the best deterministic algorithm ran in $O(n\log n)$ time. We decompose $P$ into pseudonormal histograms, then influence histograms, then $xy$ monotone histograms. We can compute the medial axes for $xy$ monotone histograms and merge to obtain the medial axis for $P$.
\itemrv{~}
\itemcc{}
\itemut{linear-time algorithm}
\itemli{doi:10.1007/PL00009429}
\end