Fronts-propagating-with-curvature-dependent-speed-

FrontsPropagatingwithCurvatureDependentSpeed:AlgorithmsBasedonHamilton-JacobiFormulationsStanleyOsher1DepartmentofMathematicsUniversityofCaliforniaLosAngeles,California90024JamesA.Sethian2DepartmentofMathematicsUniversityofCaliforniaBerkeley,California94720Wedevisenewnumericalalgorithms,calledPSCalgorithms,forfollowingfrontspropagatingwithcurvature-dependentspeed.Thespeedmaybeanarbitraryfunctionofcurvature,andthefrontcanalsobepassivelyadvectedbyanunderlyingflow.Thesealgorithmsapproximatetheequationsofmotion,whichresembleHamilton-Jacobiequationswithparabolicright-hand-sides,byusingtech-niquesfromthehyperbolicconservationlaws.Non-oscillatoryschemesofvariousordersofaccu-racyareusedtosolvetheequations,providingmethodsthataccuratelycapturetheformationofsharpgradientsandcuspsinthemovingfronts.Thealgorithmshandletopologicalmergingandbreakingnaturally,workinanynumberofspacedimensions,anddonotrequirethatthemovingsurfacebewrittenasafunction.ThemethodscanbealsousedformoregeneralHamilton-Jacobi-typeproblems.Wedemonstrateouralgorithmsbycomputingthesolutiontoavarietyofsurfacemotionproblems.1SupportedbyNSFGrantNo.,DMS85-03294,DARPAGrantintheACMPProgram,ONRGrantN00014-86-K-0691.2SupportedbytheAppliedMathematicsSubprogramoftheOfficeofEnergyResearchundercon-tractDE-AC03-76SF00098andtheNationalScienceFoundation.ThispaperappearedasOsher,S.,andSethian,J.A.,JournalofComputationalPhysics,79,pp.12-49,(1988)FrontsPropagatingwithCurvatureDependentSpeed:AlgorithmsBasedonHamilton-JacobiFormulationsI.INTRODUCTIONInavarietyofphysicalphenomena,onewantstotrackthemotionofafrontwhosespeeddependsonthelocalcurvature.Twowell-knownexamplesarecrystalgrowth[3,19,20,24,25,30,38]andflamepropagation[6,18,22,23,37,40].Inthispaper,weintroduce,analyze,andutilizeacollec-tionofnewnumericalalgorithmsforstudyingsuchproblems.Thesenewalgorithmsapproximatetheequationsofmotionofpropagatingfronts,whichresembleHamilton-Jacobiequationswithviscosityterms.Wedemonstrateouralgorithmsbycomputingthesolutionstoavarietyofsurfacemotionproblems.Thebackgroundtheoryandnumericalexperimentationbehindthisapproachhavebeendevelopedinaseriesofpapers,see[31,32,33,34].Inthispaper,theseideasarecoupledtothetech-nologyforthenumericalapproximationofhyperbolicconservationlawstoproducealgorithmswhichwecallPSCschemes,forPropagationofSurfacesunderCurvature.ThesenewschemesallowonetofollowthemotionofanN-1dimensionalsurfaceinNspacedimensions.Thespeedmaybeanarbitraryfunctionofthecurvature,andthefrontcanalsobepassivelyadvectedbyanunderlyingflow.Thealgorithmscanbeconstructedwithanydesiredaccuracyinspaceandtimeanddonotrequirethefronttoremainafunction.ThemethodsareinaEulerianframework;thusthenumberofcomputationalelementsisfixedattheoutset.Topologicalmergingandbreakingishandlednaturally,andthebasicfirstorderschemeisextremelysimpletoprogram.Asillustrationofthewideapplicabilityofsuchalgorithms,considerthecaseofflamepropa-gation,see[34].Acommonmodelidealizestheburningflameasaninfinitelythinboundarywhichseparatesregionsofconstantsteady-statevelocity,density,andtemperatureandpropagatesintotheunburntfluidataspeeddependentonthelocalcurvature.Theideahereisthatcoolconvexfingersreachingoutintotheunburntgassomehowpropagateslowerthandoconcaveregionswhicharehotgasessurroundingasmallunburntpocket.Atthesametime,particlesalongtheflamefrontundergoanincreaseinvolumeastheyburn,creatingajumpinvelocityacrosstheflamefront.Thisdiscon-tinuityinthevelocityfieldcreatesvorticityalongtheburningflame,whichcanberelatedtothelocalcurvature,andthisnewvorticityfieldcontributestotheadvectionofthepropagatingflame.Thus,thereareatleasttwodistinctwaysinwhichthespeedofthemovingflamedependsonthelocalcurvature.Typically,therehavebeentwotypesofnumericalalgorithmsemployedinthesolutionofsuchproblems.Thefirstparameterizesthemovingfrontbysomevariableanddiscretizesthisparameterizationintoasetofmarkerpoints[39].Thepositionsofthemarkerpointsareupdatedintimeaccordingtoapproximationstotheequationsofmotion.Suchtechniquescanbeextremelyaccurateintheattempttofollowthemotionsofsmallperturbations.However,forlarge,complexmotion,severalproblemssoonoccur.First,markerparticlescometogetherinregionswherethecur-vatureofthepropagatingfrontbuilds,causingnumericalinstabilityunlessaregriddingtechniqueisemployed.Theregriddingmechanismusuallycontainsaerrortermwhichresemblesdiffusionanddominatestherealeffectsofcurvatureunderanalysis.Secondly,suchmethodssufferfromtopologi-calproblems;whentworegionsburntogethertoformasingleone,ad-hoctechniquestoeliminatepartsoftheboundaryarerequiredtomakethealgorithmwork.Otheralgorithmscommonlyemployedfallunderthecategoryofvolumeoffluidtech-niques,which,ratherthantracktheboundaryofthepropagatingfront,trackthemotionoftheinte-riorregion.AnexampleofthistypeofalgorithmisSLIC[26].Inthesealgorithms,theinteriorisdiscretized,usuallybyemployingagridonthedomainandassigningtoeachcellavolumefrac-tioncorrespondingtotheamountofinteriorfluidcurrentlylocatedinthatcell.Anadvantageofsuchtechniquesisthatnonewcomputationalelementsarerequiredasthecalculationprogresses(unlikethepa