Vi föreslår en optimal tid algoritm för ett klassiskt problem i plan beräkning geometri: datorisering en kortaste väg mellan två punkter i närvaro av polygonala hinder. Vår algoritm körs i värsta fall tid O (n logn) och kräver O (n logn) utrymme, där n är det totala antalet hörn i hinderpolygoner. Algoritmen är baserad på ett eektivt genomförande av vågfrontsutbredning bland polygonala hinder, och den beräknar faktiskt en planar karta som kodar kortaste vägar från en xed källa punkt till alla andra punkter i planet; kartan kan användas för att svara på singlesource kortaste sökväg frågor i O(logn) tid. Tiden komplexiteten i vår algoritm är en signi cant förbättring över alla tidigare publicerade resultat på den kortaste vägen problem. Slutligen diskuterar vi också utvidgningar till mer allmänna problem med kortast möjliga väg, som inbegriper icke-punkts- och flera källor.
För en punkt frågor, Hershberger och Suri REF byggt en kortaste sökväg karta av O(n) storlek med O(log n) frågetid och kartan kan byggas i O (n log n) tid och utrymme.
An Optimal Algorithm for Euclidean Shortest Paths in the Plane
{'venue': 'SIAM J. Comput', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}