Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
SIGMOD RECORD 2001
CIKM 2001
= CIKM'01 Website
= CIKM'01 Papers
= CIKM Workshop_1
<<< = GIS'01 Papers>>>
= CIKM Workshop_2
= DOLAP'01 Papers
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Weighting the Path Continuation in Route Planning


Stephan Winther

  View Paper (PDF)  

Return to Inelegant Transportation Systems and Network Algorithms


Abstract

Shortest path algorithms optimize the costs of a journey in a graph. The cost function may differ; in geometric contexts for instance the travel distance, the travel time, or travel expenses are considered. Not considered so far are costs that are related to the combination of incident edges for a path. For example, if one is interested in continuing a route from a given edge with the turn of least angle, each continuation by an incident edge has to be weighted by the angle enclosed. Such cost functions produce a combinatorial complex number of weights that cannot be stored with the edges or nodes in the graph. Instead they lead to an optimization problem in a linear dual graph, for which then a shortest path algorithm can be applied.This paper gives a motivation for this kind of costs, defines the linear dual graph, presents the route-planning algorithm, and discusses its properties. Examples from guidance of pedestrians in urban environment illustrate the results.


DiSC'02 © 2003 Association for Computing Machinery