Låt G vara en n-vertex plan graf med icke-negativa kant vikter, och låt k terminal par anges på h ansikte gränser. Vi presenterar en algoritm för att hitta k icke-crossing promenader i G av minsta totala längd som ansluter alla terminalpar, om några sådana promenader finns, i 2 O(h 2 ) n log k tid. De beräknade promenaderna kan överlappa varandra men får inte korsa varandra eller sig själva. Vår algoritm generaliserar ett resultat av Takahashi, Suzuki och Nishizeki [Algorithmica 1996] för specialfallet h ≤ 2. Vi beskriver också en algoritm för motsvarande geometriska problem, där terminalpunkterna ligger på gränsen av h polygonala hinder av total komplexitet n, återigen i 2 O(h 2 ) n tid, generalisera en algoritm av Papadopoulou [Int. Det är J. Comput. Geom. Applicering. 1999] för specialfallet h ≤ 2. I båda inställningarna, kortaste icke-crossing promenader kan ha komplexitet exponentiellt i h. Vi beskriver också algoritmer för att avgöra i O(n) tid om terminalparen kan anslutas genom någon icke-crossing promenader.
Erickson och Nayyeri REF utvidgade detta till punkter på gränserna för h polygonala hinder.
Shortest non-crossing walks in the plane
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}