Abstrakt. Med tanke på en uppsättning icke-intersecting polygonala hinder i planet, länken avståndet mellan två punkter s och t är det minsta antalet kanter som krävs för att bilda en polygonal väg ansluter s till t som undviker alla hinder. Vi presenterar en algoritm som beräknar länkavståndet (och en motsvarande minsta länkväg) mellan två punkter i tiden O(Ect(n) log 2 n) (och utrymme O(E)), där n är det totala antalet kanter av hindren, E är storleken på synlighetsgrafen, och c~n) betecknar den extremt långsamt växande inversen av Ackermanns funktion. Vi visar hur vi utökar vår metod för att möjliggöra beräkning av ett träd (rotat på s) av minimala länkvägar från s till alla hinder hörn. Detta leder till en metod för att lösa frågeversionen av vårt problem (för frågepunkter t).
För att hitta en minsta länk s-t-bana mellan två punkter s och t i en godtycklig polygonal domän P gav Mitchell REF en O(Eα(n) log 2 n) tidalgoritm, där α(n) är motsatsen till Ackermanns funktion och E är storleken på synbarhetskurvan för P och E =  på 2 ) i värsta fall.
Minimum-link paths among obstacles in the plane
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}