MATHEMATICAL THEORY OF MEDIAL AXIS

pacificjournalofmathematicsVol.181,No.1,1997MATHEMATICALTHEORYOFMEDIALAXISTRANSFORMHyeongInChoi,SungWooChoiandHwanPyoMoonThemedialaxisofaplanedomainisdenedtobethesetofthecentersofthemaximalinscribeddisks.Itisessentiallythecutlocioftheinwardunitnormalbundleoftheboundary.Weprovethatifaplanedomainhasnitenumberofboundarycurveseachofwhichconsistsofnitenumberofrealanalyticpieces,thenthemedialaxisisaconnectedgeometricgraphinR2withnitelymanyverticesandedges.AndeachedgeisarealanalyticcurvewhichcanbeextendedintheC1mannerattheendvertices.Weclarifytherelationbetweenthevertexdegreeandthelocalgeometryofthedomain.Wealsoanalyzevariouscontinuityandregularityresultsindetail,andshowthatthemedialaxisisastrongdeformationretractofthedomainwhichmeansinthepracticalsensethatitretainsallthetopologicalinformationsofthedomain.Wealsoobtainparallelresultsforthemedialaxistransform.1.Introduction.Oneofthedicultproblemsinglobaldierentialgeometryistheprecisedescriptionandtheexactdeterminationofthecutlociofaset.Itisbecauseacutlocusarisesasacriticalpointofacertaindistancefunction,andstudyingitisingeneralanontrivialproblem.Inthispaper,westudythefollowingversion:LetΩbeaconnectedboundeddomaininR2.LetCORE(Ω)bethesetofthemaximalinscribeddisksinΩ.Wedenethemedialaxis,denotedbyMA(Ω),tobethesetofthecentersofthedisksinCORE(Ω).ThusifΩhassmoothboundary,MA(Ω)isessentiallythesetofthecutlocioftheinwardpointingunitnor-malbundleof@Ω.ButsinceweallowΩtohavecorners,ourcaseincludesaslightlymoregeneralnotion.(ConsultDenition4:4anditssubsequentrole.)Wecanalsodenethemedialaxistransform,denotedbyMAT(Ω),tobethesetofthepairsconsistingofthecenterandtheradiusofthedisksinCORE(Ω).Themedialaxisisacontinuousversionoftheso-calledVoronoidiagramwhichwasintroducedbyVoronoi[14].Voronoidiagramwasoriginallyde-nedforanitesetofpointsinR2,andinfactthisandtherelatednotionscanbetracedasfarbackastoDirichlet[3].5758HYEONGINCHOI,SUNGWOOCHOIANDHWANPYOMOONAlthoughthemedialaxisisanaturalgeometricobject,itscarefulmathe-maticalstudyhasbeenlackinginthepuremathematicscommunities.How-ever,themedialaxistransformhasbeenwidelyusedintheengineeringandthecomputersciencecommunity.Themodernincarnationoftheme-dialaxistransformwasintroducedbyBlum[1]toextractandrepresentthesalientfeaturesofaplanarshape(domain).Sincethen,therehasbeenaprolicamountofliteraturesinmanyapplicationareassuchasvision,pat-ternrecognition,NCtoolpathplanning,andFEMmeshgeneration,andsoon.However,theengineeringandthecomputersciencecommunitiesaremainlyinterestedinthealgorithmicaspectsofactuallyndingthemedialaxistransformunderspecicconditionsonthedomain,andtheyseemtobelessinterestedinpinningdowntheintricatemathematicaldetailsforgeneralclassofdomains.Mostoftheknownresultsdealwiththedomainwiththeboundaryconsistingoflinesegmentsandpiecesofcirculararcs.Thesecanbefoundin[5,8,9,10,13,16],tonameafew.However,evenintheapplicationareas,theboundarycurvesneedtobeofmuchmoregeneralform.ThekindofcurverepresentationacceptedasthemostgeneralinapplicationiscalledtheNURBS,i.e.,Non-UniformRationalB-Splines.Mathematically,theyariseassplinesintheprojectivegeometry,andtheyareallrationalfunctionsofthecurveparameter,But,inthisgenerality,notsomuchisknownforthemedialaxistransform.OurpaperwithN.-S.Wee[2]givesagoodapproximatealgorithmwhichworkswellinpracticalsituationswithverygeneralboundarycurveassumptions,i.e.,boundaryisassumedtobecomposedofnitenumberofrealanalyticcurves.Inprovingthatouralgorithmworksandterminatesinnitesteps,etc.,wehadtohavetherigorousmathematicalfoundation.Asweponderedovertheseissues,wediscoveredmanyinterestingpiecesofmathematics.Thispaperisanoutgrowthofthat.Oneimportantobservationthatisrelevanttooursubsequentanalysisistheregularityassumptionofthedomain.Contrarytocommonbelief,itisnotenoughtoassumethattheboundarycurveisC1.Infact,weshowthatthereareplentyofdomainswithC1boundarythathavepathologicalbehavior.Forexample,therearedomainswithC1boundarythathaveinnitelymanyinscribedosculatingcircles,orinnitelymanybifurcationcircles.Or,theymayhaveamedialaxispointfromwhichinnitelymanybranchesofthemedialaxisemanate.Thesemaymakethemedialaxisaninnitegraph.Infact,itispossibletocreateallkindsofpathologicalexampleswiththeC1assumptionontheboundary.Thuswehavetorestricttheclassofdomainsinordertodomeaningfulanalysis.Thedomainsweconsideraretheoneswithnitelymanyboundarycurveseachofwhichconsistsofnitenumberofrealanalyticpieces.TheMEDIALAXISTRANSFORM59realanalyticpiecesintheboundarymaymeetwitheachotherintheC1manner,ormaymeetatacorner.Thiskindofrestrictionsposenoreallossinmostpracticallyimportantsituations,sincealmostalldomainsthathavepracticalimportancehavethisproperty.Forinstance,theboundarycurvesmayberepresentedasNURBScurveswhichfallintothiscategory.Wecannothelpbelievingthatourassumptionisthemostnaturalandoptimalinpractice.Thebasicstrategyofouranalysisisajudiciouscombinationoflocaldif-ferentialgeometryandsomeofthetoolswedevelop.ThemostimportanttoolistheDomainDecompositionLemmawhichenablesustobreakupthedomainintosimplerpieces,thuslocalizingtheanalysis.Wea