NEW ALGORITHM FOR MEDIAL AXIS TRANSFORM OF PLANE DOMAIN

In this paper, we present a new approximate algorithm for medial axis transform of a plane domain. The underlying philosophy of our approach is the localization idea based on the Domain Decomposition Lemma, whi ch enables us to break up the complicated domain into smaller and simp ler pieces. We then develop tree data structure and various operations on it to keep track of the information produced by the domain decompo sition procedure. This strategy enables us to isolate various importan t points such as branch points and terminal points. Because our data s tructure guarantees the existence of such important points-in fact, ou r data structure is devised with this in mind-we can zoom in on those points. This makes our algorithm efficient. Our algorithm is a ''from within'' approach, whereas traditional methods use a ''from-the-bounda ry'' approach. This ''from within'' nature of our algorithm and the lo calization scheme help mitigate various instability phenomena, thereby making our algorithm reasonably robust. (C) 1997 Academic Press.