Connection errors in networks of linear features and the application of geometrical reduction in spatial data algorithms

We present a study on connection errors in networks of linear features and methods of error detection. We model networks with special connection specifications as networks with hierarchically connected features and define errors considering the spatial relationships and the functionality of the network elements. A general definition of the problem of the detection of connection errors which takes into account the functionality of the network elements is discussed. Then a series of spatial algorithms that solve different aspects of the problem is presented. We also define and analyze the notion of geometrical reduction as a method of achieving efficient performance. In the last section the undecidability of algorithmic error correction is discussed.