I detta dokument studeras verkliga vägnät ur ett algoritmiskt perspektiv, med fokus på empiriska studier som ger användbara egenskaper hos vägnät som kan utnyttjas i designen av snabba algoritmer som hanterar geografiska data. Till skillnad från tidigare tillvägagångssätt är vår studie inte baserad på antagandet att vägnät är plana grafer. Baserat på ett antal experiment som vi har utfört på vägnäten i de 50 Förenta staterna och District of Columbia, ger vi starka empiriska bevis för att vägnäten är helt oplanerade. Vår strategi är därför istället inriktad på att hitta algoritmiskt motiverade egenskaper hos vägnät som icke-planära geometriska grafer, med fokus på alternativa egenskaper hos vägnät som fortfarande kan leda till effektiva algoritmer för sådana problem som kortaste vägar och Voronoidiagram. I synnerhet studerar vi vägnät som multiscale-dispergerade grafer, vilket är ett koncept som vi formaliserar i termer av disk grannskapssystem. Detta tillvägagångssätt gör att vi kan utveckla snabba algoritmer för vägnät utan att göra några ytterligare antaganden om fördelningen av kantvikter. I själva verket, våra algoritmer kan tillåta icke-metriska vikter.
Eppstein och Goodrich REF inledde en studie av vägnät i termer av att de betraktas som särskilda typer av geometriska grafer som kallas multiscale-dispergerade grafer och de gav empiriska belägg för att verkliga vägnät i själva verket är fall av sådana grafer.
Studying (non-planar) road networks through an algorithmic lens
{'venue': "GIS '08", 'journal': None, 'mag_field_of_study': ['Computer Science']}