Extended Abstract

DRAFT:MinimumWeightConvexQuadrangulationofaConstrainedPointSetThomasFevensHenkMeijerDavidRappaportDepartmentofComputingandInformationScienceQueen’sUniversityatKingston,Kingston,OntarioK7L3N6Canada.Email:[e-mail]5,1997ExtendedAbstractSummary:AconvexquadrangulationwithrespecttoapointsetSisaplanarsubdivi-sionwhoseverticesarethepointsofS,wheretheboundaryoftheunboundedouterfaceistheboundaryoftheconvexhullofS,andeveryboundedinteriorfaceisconvexandhasfourpointsfromSonitsboundary.AminimumweightconvexquadrangulationwithrespecttoSisaconvexquadrangulationofSsuchthatthesumoftheEuclideanlengthsoftheedgesofthesubdivisionisminimised.Inthisextendedabstract,wewillpresentapolynomialtimealgorithmtodeterminewhetherasetofpointsSadmitsaconvexquadrangulationifSisconstrainedtolieonaxednumberofnestedconvexpolygons,wherethetimecomplexityispolynomialinthecardinalityofS.Thisalgorithmcanalsobeusedtondaminimumweightconvexquadrangulationofthepointset.WeuseasimilarapproachtoconstructaconvexsubdivisionwithrespecttoSusingthreeorfourpointsfromSperface,andminimisingthetotalnumberoffaceswithintheboundaryoftheconvexhullofS.1IntroductionTherearemanyproblemsforwhichitisnecessarytondanumericalsolutionofacomplicatedsystemofdierentialequations.Tondsuchanumericalsolution,theniteelementmethod[6][20]isoftenemployed.Withthismethod,thedomainoverwhichthesolutionissoughtisdividedintosmallpieces(niteelements)determinedbydatapointssampledfromthedomain.Thissubdivision,oftengeneratedautomaticallyorsemi-automatically,istermedamesh.Typically,themeshiscomprisedoftriangularniteelements,butforsomesituations,suchasforinterpolatingscattereddata[11][12]aswellasforsomeniteelementmethodapplications[3][7],itispreferabletouseniteelementsthatarequadrangles(quadrilaterals)insteadoftriangles.SuchaquadrangulationwithrespecttoapointsetSisaplanarsubdivisionwhoseverticesarethepointsofS,wheretheboundaryoftheunboundedouterfaceistheboundaryoftheconvexhullofS,andeveryboundedinteriorfacehasfourpointsfromSonitsboundary.AconvexquadrangulationwithrespecttoapointsetSisaquadrangulationofSsuchthatallthequadranglesareconvex.Aminimumweight(minimum\ink)convexquadrangulationwithrespecttoapointsetisaconvexquadrangulationofSsuchthatthesumoftheEuclideanlengthsofthelinesegmentsofthequadrangulationisminimised.Inthisabstract,ourprimaryresultwillbeapolynomialtimealgorithmtondaminimumweightconvexquadrangulation(MWCQ)ofaplanarpointsetconstrainedtowhatisknownasaconstantnumberofnestedconvexhulls.12PreliminariesBeforewecontinue,letusintroducesometerminologyusedinthisabstract.Mostofthegeometricterminologyisstandardanddetailscanbefoundin[15].LetE2denotetheEuclideanspaceintwodimensions.WeassumethatanygivenpointsetSisingeneralposition,i.e.,nothreepointsarecollinear.Denition2.1Let(x;y)denotetheclosedundirectedlinesegment,oredge,betweenverticesxandy.Dened(x;y)tobetheweightof(x;y).FortheMWCQalgorithm,thisweightwillbetheEuclideandistancebetweenxandy.Denition2.2AdomaininE2isconvexifforanytwopointsp1andp2inthedomain,(p1;p2)doesnotcrosstheboundaryofthedomain.Denition2.3ApolygonPistheclosedregionoftheplaneboundedbyanitecollectionoflinesegmentsformingasimple(notself-intersecting)closedcurve.WewillusethenotationPtodenotetheboundaryofP.Denition2.4ConsiderasimplepolygonP.ConsiderapointxPandapointyintheplane.Wesaythatxcanseey,oryisvisibletox,if(x;y)P.Denition2.5Givenasetofpoints,S,anemptypolygonisapolygonwithnopointsfromSinitsinterior.Denition2.6Astar-shapedpolygonPisanemptypolygonwherethereexistsatleastonepointxPsuchthatxcanseetheentireinteriorofthepolygon.Denition2.7Anorthogonalpolygonisapolygonwhoseedgesofitsboundaryareparalleltotwoorthogonalaxes.Denition2.8Givenasetofpoints,S,theconvexhullofS,denotedasCH(S),isdenedtobetheminimumareaconvexpolygonenclosingS.Denition2.9ConsiderasimplepolygonP.LetSbeapointsetintheplaneincludingtheverticesoftheboundaryofP.ThequadrangulationofPisaplanarsubdivisionwhoseverticesareS\Pandwhereeveryfaceinteriortothepolygonboundaryisboundedandisaquadrangle.ThequadrangulationofanemptypolygonwouldbeaspecialcasewhereS\PonlyincludestheverticesofP.23PreviousWorkThepossiblenumberofquadrangulationsforagivenemptypolygonPcanbeexponentialinthenumberofverticesontheboundaryofP[10],althoughanarbitrarysimpleemptypolygonmaynotevennecessarilyadmitaquadrangulation.Inoneoftheearlierquadrangulationresults,actuallymotivatedbyitsapplicationinlocatingn=4guardstocover(i.e.,watchover)theinteriorofanemptypolygonwithnvertices,SackandToussaint[18]showedthattheycouldpartitionarectilinearstar-shapedpolygonintoconvexquadranglesinO(n)time.Kahn,KlaweandKleitman[8]thengaveanexistentialproofthatarbitrarysimpleorthogonalemptypolygonscanbepartitionedintoconvexquadrangles.Theyalsoshowedthatanyorthogonalpolygonwithnverticesandhholescanbedecomposedinton=2+h1convexquadrangles.Followinguponthis,Sack[17],SackandToussaint[19],andindependentlyLubiw[13]allgaveconstructiveproofsofKahn,KlaweandKleitman’sexistentialproof.ThetimecomplexityoftheiralgorithmswasO(nlogn).Also,Lubiwsh