Data structures for topological and geometric operations on networks

N. Christofides, H.O. Badra and Y.M. Sharaiha

Annals of Operations Research, 1997, vol. 71, issue 0, 259-289

Abstract: The growing interest in computer graphics and Geographical Information Systems has made it necessary to develop efficient data structures and algorithmic procedures for handling graphical information in real-time. In this paper, we consider the problem of storage and manipulation of large-scale networks which can undergo dynamic changes. Two complementary data structures are presented: a topological and a topographical representa-tion. The objective is to support both graph-theoretic and geometric operations efficiently. A topological representation facilitates the implementation of graph-theoretic optimization algorithms such as the shortest path and spanning tree problems. In this context, a new dynamic forward star structure is developed and contrasted with the classic (static) forward star representation of sparse graphs. Algorithmic procedures and complexity analysis for network editing operations of this structure are provided. A topographical representation is necessary for geometric operations such as nearest neighbour location and range retrieval. Algorithms for performing editing and geometric operations on the BD-tree are presented. Finally, the practical efficiency of the data structures is investigated by computational experiments on large-scale road networks. Copyright Kluwer Academic Publishers 1997

Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018971515573 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:71:y:1997:i:0:p:259-289:10.1023/a:1018971515573

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018971515573

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().