Vi föreslår en algoritm för problemet med att beräkna kortaste vägar bland böjda hinder i planet. Om hindren har O(n) beskrivning komplexitet, då algoritmen körs i O (n log n) tid plus en term som är beroende av egenskaperna hos gränsbågarna. Specifikt, om bågen tillåter en viss typ av bisector skärningspunkt att beräknas i konstant tid, eller även i O(log n) tid, då körtiden för den totala algoritmen är O (n log n). Om båge stöder endast konstant-tid tangent, skärningspunkt och längd frågor, som vanligtvis antas, då algoritmen beräknar en ungefärlig kortaste sökväg, med relativa fel ε, i tid O(n log n + nlog 1 ε ). I själva verket beräknar algoritmen en ungefärlig kortaste sökväg, en datastruktur med O(n log n) storlek, som gör det möjligt att rapportera (ungefär) längden av en kortaste sökväg från en fast källpunkt till någon frågepunkt i planet i O(log n) tid.
Genom att använda det kontinuerliga Dijkstra ramverket, Hershberger et al. REF presenterar en O(n log n) tid för SPSD, under vissa antaganden om beräkningen av lokaliseringen av skärningspunkten mellan två "bisektorer", utan antagandet, deras tillvägagångssätt kan beräkna en (1 + )-faktor ungefärlig kortaste vägen för SPSD i O (n log n + n log 1 ) tid.
A near-optimal algorithm for shortest paths among curved obstacles in the plane
{'venue': "SoCG '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}