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

Network Planning using Geomorphology


Ingo Petzold, Gerhard Gröger, and Lutz Plümer

  View Paper (PDF)  

Return to Inelegant Transportation Systems and Network Algorithms


Abstract

Connecting several locations, for example towns by roads, is a typical network planning problem. A first approach would be to connect pairs of nodes (network language term for location) with a straight edge. The result is a connected network not considering the total network length and the average trip length. The construction of new junctions, so called Steiner Points, for reducing the total network length and thereby the global costs is more or less known. On the other hand slopes, obstacles or other unsteady costs can not be taken into account during construction. Therefore an independent and homogeneous representation for costs and network planning is necessary.Our approach distinguishes between topographical and additional costs, for example nature reserves and restricted areas. The proposed representation of the topography in a digital terrain model (DTM) is a constrained delaunay triangulated irregular network (TIN). The initial problem of connecting different locations is at the first sight reduced to the shortest path problem, taking the extra attributes into account. But these algorithms are not suitable to connect more than two locations.In this paper we will show how to use the information of a slightly extended Dijkstra Shortest-path algorithm to classify the nodes of the TIN and identify candidates for Steiner Points. Assuming that each geomorphologically closed area can be represented by one Steiner Point, the presented algorithm leads to an optimal network. Steiner Points, passes and the shortest paths between the latter constitute the basis for a network, which provides cheapest connections with regard to topographical costs.To avoid exhaustive searching, geomorphology of the DTM is used as a powerful heuristic. It leads to a partitioning of the space and as a result to a divide- and conquer strategy.


DiSC'02 © 2003 Association for Computing Machinery