Abstract.
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 .
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received May 16, 1997, and in revised form October 30, 1997.
Rights and permissions
About this article
Cite this article
Chin, F., Snoeyink, J. & Wang, C. Finding the Medial Axis of a Simple Polygon in Linear Time . Discrete Comput Geom 21, 405–420 (1999). https://doi.org/10.1007/PL00009429
Issue Date:
DOI: https://doi.org/10.1007/PL00009429