G. Pipan and B. Slivnik (Slovenia)
minimum weight triangulation, distributed incremental al gorithms.
A distributed heuristic algorithm for computing approximations of the minimum weight triangulation of a set of points in Euclidean plane, is described. The new algorithm, named DWT, is incremental and can add multiple points to the existing triangulation simultaneously. The algorithm needs less information about the neighbourhood of the point being added than, for instance, LMT heuristic algorithm. The quality of the produced approximations is measured experimentally and compared against the LMT heuristics. As the algorithm is designed so that every point is placed on its own node in a distributed system, the algorithm is perfectly suited for constructing triangulated over lay networks on the fly.
Important Links:
Go Back
