Efficient Algorithms for Diffusion-Generated Motio

EFFICIENTALGORITHMSFORDIFFUSION-GENERATEDMOTIONBYMEANCURVATUREByStevenJ.RuuthBMATH,UniversityofWaterloo,1991MSc,UniversityofBritishColumbia,1993athesissubmittedinpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophyinthefacultyofgraduatestudiesdepartmentofmathematicsandInstituteofAppliedMathematicsWeacceptthisthesisasconformingtotherequiredstandard::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::theuniversityofbritishcolumbiaAugust1996cStevenJ.Ruuth,1996InpresentingthisthesisinpartialfullmentoftherequirementsforanadvanceddegreeattheUniversityofBritishColumbia,IagreethattheLibraryshallmakeitfreelyavailableforreferenceandstudy.Ifurtheragreethatpermissionforextensivecopyingofthisthesisforscholarlypurposesmaybegrantedbytheheadofmydepartmentorbyhisorherrepresentatives.Itisunderstoodthatcopyingorpublicationofthisthesisfornancialgainshallnotbeallowedwithoutmywrittenpermission.DepartmentofMathematicsTheUniversityofBritishColumbia2075WesbrookPlaceVancouver,CanadaV6T1W5Date:AbstractThisthesisconsiderstheproblemofsimulatingthemotionofevolvingsurfaceswithanormalvelocityequaltomeancurvatureplusaconstant.Suchmotionsariseinavarietyofapplications.AgeneralmethodforthispurposewasproposedbyMerriman,BenceandOsher,andconsistsofalternatelydiusingandsharpeningthefrontinacertainmanner.Thismethod(referredtoastheMBO-method)naturallyhandlescomplicatedtopologicalchangeswithjunctionsinseveraldimensions.However,theusualnitedif-ferencediscretizationofthemethodisoftenexceedinglyslowwhenaccurateresultsaresought,especiallyinthreespatialdimensions.Weproposeanew,spectraldiscretizationoftheMBO-methodwhichobtainsgreatlyimprovedeciencyovertheusualnitedierenceapproach.Theseeciencygainsareobtained,inpart,throughtheuseofaquadrature-basedrenementtechnique,byin-tegratingFouriermodesexactly,andbyneglectingthecontributionofrapidlydecayingsolutiontransients.Theresultingmethodprovidesapracticaltool,notavailablehitherto,foraccuratelytreatingthemotionbymeancurvatureofcomplicatedsurfaceswithjunc-tions.Indeed,wepresentnumericalstudieswhichdemonstratethatthenewalgorithmisoftenmorethan1000timesfasterthantheusualnitedierencediscretization.Newanalyticandexperimentalresultsarealsodevelopedtoexplainimportantprop-ertiesoftheMBO-methodsuchastheorderoftheapproximationerror.Extrapolatedalgorithms,notpossiblewhenusingtheusualnitedierencediscretization,areproposedanddemonstratedtoachievemoreaccurateresults.Weapplyournew,spectralmethodtosimulatethemotionofanumberofthreedimensionalsurfaceswithjunctions,andwevisualizetheresults.Wealsoproposeandstudyasimpleextensionofourmethodtoanonlocalcurvaturemodelwhichisimpracticaltotreatusingthepreviouslyavailablenitedierencediscretization.iiTableofContentsiiListofFiguresviAcknowledgementsix1Introduction11.1Curvature-DependentMotion::::::::::::::::::::::::11.2MethodsforCurvature-DependentMotion:::::::::::::::::41.3Overview::::::::::::::::::::::::::::::::::::82Diusion-GeneratedMotionbyMeanCurvatureAlgorithm102.1TheTwoPhaseProblem:::::::::::::::::::::::::::102.2MultipleJunctions::::::::::::::::::::::::::::::132.3Selectionof:::::::::::::::::::::::::::::::::162.4FiniteDierenceDiscretizationsoftheMBO-Method:::::::::::172.4.1SelectionofaTime-SteppingMethod::::::::::::::::172.4.2LimitationsofFiniteDierenceDiscretizations:::::::::::183ANew,SpectralMethod243.1DiscretizationoftheHeatEquation:::::::::::::::::::::243.2CalculationoftheFourierCoecients::::::::::::::::::::263.3ApproximationoftheFinestSubregions::::::::::::::::::303.3.1TrivialTreatmentoftheFinestSubregions:::::::::::::30iii3.3.2PiecewiseLinearApproximationforTwo-PhaseProblems:::::313.3.3PiecewiseLinearApproximationsforJunctions::::::::::393.4RenementTechniques::::::::::::::::::::::::::::433.4.1TheOriginalRenementAlgorithm:::::::::::::::::433.4.2AMethodforaGradualRenement::::::::::::::::473.5Fast,Transform-BasedAlgorithms::::::::::::::::::::::493.5.1Overview:::::::::::::::::::::::::::::::523.5.2TheUnequallySpacedFastFourierTransform:::::::::::533.6ComparisontotheUsualFiniteDierenceDiscretization:::::::::574TheoreticalandNumericalStudies604.1SmoothInterfaces:::::::::::::::::::::::::::::::604.1.1TruncationErrorAnalysis::::::::::::::::::::::614.1.2Extrapolation:::::::::::::::::::::::::::::634.1.3NumericalExperiments::::::::::::::::::::::::644.2NonsmoothBoundaries::::::::::::::::::::::::::::664.3SingularitiesintheSolutionasRegionsDisappear:::::::::::::694.4JunctionsinTwoDimensions::::::::::::::::::::::::704.4.1ErrorAnalysis:::::::::::::::::::::::::::::714.4.2NumericalExperiments::::::::::::::::::::::::774.5Summary:::::::::::::::::::::::::::::::::::805NumericalExperimentsandVisualization825.1ThreeDimensional,Two-PhaseProblems::::::::::::::::::825.1.1Visualization:::::::::::::::::::::::::::::825.1.2NumericalExperiments::::::::::::::::::::::::865.2JunctionsinThreeDimensions:::::::::::::::::::::::87iv5.2.1Visualization::::::::::::::::::::::::::