Sammanfattning av denna webbsida: Vägnätsanalys kan kräva avstånd från punkter som inte finns på själva nätet. Vi studerar det algoritmiska problemet med att ansluta en punkt inuti ett ansikte (region) av vägnätet till dess gräns samtidigt minimera avstickaren faktor av den punkten till någon punkt på gränsen av ansiktet. Vi visar att den optimala enda anslutningen (feed-link) kan beräknas i O(λ 7 (n) log n) tid, där n är antalet hörn som begränsar ansiktet och λ 7 (n) är den något superlinjära maximala längden av en DavenportSchinzel sekvens av ordning 7 på n symboler. Vi presenterar också approximativa resultat för att placera fler feed-links, hantera fallet att det finns hinder i ansiktet på vägnätet som innehåller den punkt som ska anslutas, och presentera olika relaterade resultat.
Aronov m.fl. REF presenterar algoritmer för följande problem: med tanke på en punkt inuti en polygon, beräkna ett segment från punkten till gränsen för polygonen så att dilatationen från den givna punkten till någon punkt på gränsen minimeras.
Connect the dot: Computing feed-links for network extension ∗
{'venue': 'J. Spatial Information Science', 'journal': 'J. Spatial Information Science', 'mag_field_of_study': ['Psychology', 'Computer Science']}