A compact piecewise-linear Voronoi diagram for con

ACompactPiecewise-LinearVoronoiDiagramforConvexSitesinthePlaneMichaelMcAllisterDavidKirkpatrickJackSnoeyinkDepartmentofComputerScienceUniversityofBritishColumbiaAbstractIntheplanethepost-oceproblem,whichasksfortheclosestsitetoaquerysite,andretractionmotionplanning,whichasksforaone-dimensionalretractofthefreespaceofarobot,arebothclassicallysolvedbycomput-ingaVoronoidiagram.Whenthesitesarekdisjointconvexsets,wegiveacompactrepresentationoftheVoronoidiagram,usingO(k)linesegments,thatissucientforlogarithmictimepost-ocelocationqueriesandmotionplanning.Ifthesesetsarepolygonswithntotalverticesgiveninstandardrepresentations,wecomputethisdiagramoptimallyin(klogn)determin-istictimefortheEuclideanmetricandinO(klognlogm)deterministictimefortheconvexdistancefunctiondenedbyaconvexm-gon.1IntroductionOneoftheearliestsuccessesofcomputationalgeometryistheO(nlogn)timecomputationoftheVoronoidiagramofnpointsitesintheplane,whichisthepartitionoftheplaneintomaximallyconnectedregionsthathavethesamesetofclosestsites[29,34].Aurenhammer[3]hassurveyedthemanyapplicationsandgeneralizationsoftheVoronoidiagram.Inthispaperweconcentrateontwoclassicalapplications|thepost-oceproblemandthe\retractionmethodforplanningtranslationalmotion|whenthesitesarekdisjointconvexpolygonswithatotalofnvertices.ThisworkhasbeensupportedbyNSERCintheformofaGraduateScholarshipandtwoResearchGrants.11.1Thepost-oceproblemandretractionmotionplanningThepost-oceproblem[34]takesasetofksitesintheplaneandasksforadatastructure,basedonthesesites,suitableforecientlydeterminingtheclosestsitetoanarbitraryquerypoint.Whenthesitesaredisjointconvexpolygonswithntotalvertices,theVoronoidiagramhaskfacesboundedbyO(n)segmentsoflinesandparabolas[22,25,37].Combinedwithadatastructureforpointlocation[15,19,31],itgivesanO(n)spacedatastructurethatanswersqueriesinO(logn)timeafterO(nlogn)preprocessing.Theretractionmethodformotionplanning[2,28,32]usestheVoronoidiagramofksitestodetermineifthereexistsamotionofthecentreofadiskfromaninitialpositionptoanalpositionqthatdoesnotcausethedisktointersectanysite.BecauseeachedgeoftheVoronoidiagramisequidistantfromitstwoclosestsites,maximum-clearancepaths,whichmaximizetheminimumdistancetoanobstacle,canfollowVoronoiedges.AfterO(nlogn)preprocessingonecanobtainanO(n)spacedatastructurethatcanbeusedtodetermine,inO(logn)time,ifmotionfromptoqispossibleandtoconstructamaximum-clearancepathintimeproportionaltothepathcomplexity[30].Furthermore,bygeneralizingthedistancemeasurefromtheEuclideanmetrictoaconvexdistancefunction,onecancomputearetractiondiagramfortranslatingaconvexobject.(Weelaborateinsection2.3.)AlthoughtheVoronoidiagramisoptimalforboththepost-oceproblemandforretractionmotionplanningforpointsites,itcanbeexcessivelyelaboratewhenthesitesarepolygons.Supposethatwehavekpolygonalsiteswithatotalofnvertices(wesaythesiteshavetotalcomplexityn).TheedgesoftheVoronoidiagramconsistofO(n)segmentsoflinesandparabolas.Answeringapost-ocequerytheninvolvessearchingthroughparabolicandstraight-linesegmentstondtheVoronoicellthatcontainsthequerypoint.RetractionmotionplanningpathsontheVoronoidiagramaskarobottotraversepiecesoflinesegmentsandparabolas.WewouldlikeasimplerversionoftheVoronoidiagramthatletsussolvethepost-oceproblemandretractionmotionplanningforpolygonalsiteswhileavoidingtheO(n)complexityoftheVoronoidiagram.ThispaperdescribesacompactapproximationoftheVoronoidiagramwhentheksitesaredisjointconvexpolygonswithntotalvertices.Thecompactdiagram2iscomposedofO(k)linesegmentsandissucienttosolvethepost-oceprobleminO(logn)timeandretractionmotionplanningproblemsinO(logk)time.Iftheverticesofeachsitepolygonarerepresentedasorderedlistsinarraysorbalancedsearchtrees,wecancomputethediagramdeterministicallyin(klogn)timebyasweepalgorithm,asshowninsection3.ThecompactdiagramcanalsorepresentthegeneralizedVoronoidiagramde-nedbyaconvexdistancefunction[11].Forkdisjointconvexpolygonswithtotalcomplexitynandthedistancefunctioninducedbyaconvexm-gon,theVoronoidiagramcanhave(n+km)complexity.OurdiagramwithO(k)linesegmentscanbecomputedinO(klognlogm)timeandcananswerpost-ocequeriesinO(logn+logm)timeandmotionplanningqueriesonO(logk)time.Thisdiagramhasseveraladvantagesbesidesitsecientdeterministicconstruc-tion.First,giventhecompactdiagram,thetrueVoronoidiagramcanbederivedintimeproportionaltoitscomplexity((n)fortheEuclideanand(n+km)forconvexdistancefunctions).Second,forapplicationswhereknowingtwocan-didatesfortheclosestsite(andnottheirdistances)issucient,onecandiscardtheoriginalsites(anddistancefunction)andstoreonlytheO(k)segmentsofthecompactdiagram.Retractionmotionplanningisonesuchapplication.Third,becausethecompactdiagramisentirelycomposedoflinesegments,thecompactdiagramiseasiertocompute,display,andtraversethantheVoronoidiagram.Thisisanadvantageeveniftheksitesarelinesegments.Theremainderofthissectioncomparesourdiagramtorelatedworkonthedenitionandconstructionof(compact,generalized,andabstract)Voronoidia-grams.Formoredetail,seeAurenhammer’ssurvey[3].Section2describesthediagramanditsapplica