Finding the medial axis of a simple polygon in linear time

Authors
Chin, F Snoeyink, J Wang, CA
Citation
F. Chin et al., Finding the medial axis of a simple polygon in linear time, DISC COM G, 21(3), 1999, pp. 405-420
Citations number
29
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE & COMPUTATIONAL GEOMETRY
ISSN journal
01795376 → ACNP
Volume
21
Issue
3
Year of publication
1999
Pages
405 - 420
Database
ISI
SICI code
0179-5376(199904)21:3<405:FTMAOA>2.0.ZU;2-D
Abstract
We give a linear-time algorithm for computing the medial axis of a simple p olygon P. This answers a long-standing open question-previously, the best d eterministic algorithm ran in O(n log n) time. We decompose P into pseudono rmal histograms, then influence histograms, then ny monotone histograms. We can compute the medial axes for xy monotone histograms and merge to obtain the medial axis for P.