A Growing Self-Organizing Network for Reconstructing Curves and Surfaces

In the original Self-Organizing Map (SOM) algorithm by Teuvo Kohonen [1] a lattice of connected units learns a representation of an input data distribution. During the learning process, the weight vector - i.e. a position in the input space - associated to each unit is progressively adapted to the input distribution by finding the unit that best matches each input and moving it'closer' to that input, together with a subset of neighboring units, to an extent that decreases with the distance on the lattice from the best matching unit. As the adaptation progresses, the SOM tends to represent the topology input data distribution in the sense that it maps inputs that are'close' in the input space to units that are neighbors in the lattice. In the Neural Gas (NG) algorithm [2], the topology of the network of units is not fixed, as it is with SOMs, but is learnt from the input distribution as part of the adaptation process. In particular, Martinetz and Schulten have shown in [3] that, under certain conditions, the Neural Gas algorithm tends to constructing a restricted Delaunay graph, namely a triangulation with remarkable topological properties to be discussed later. They deem the structure constructed by the algorithm a topology representing network (TRN). Besides the thread of subsequent developments in the field of neural networks, the work by Martintetz and Schulten have raised also a considerable interest in the community of computational topology and geometry. The studies that followed in this direction have produced a number of theoretical results that are nowadays at the foundations of some popular methods for curve and surface reconstruction in computer graphics ([4]), although they have little or nothing in common with neural networks algorithms.