An incremental algorithm for distributed minimum weight triangulation
Gregor Pipan, Boštjan Slivnik · International Conference on Parallel and Distributed Computing and Networks · 2008
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 overlay networks on the fly.