Title:	Genetic approach to the minimum weight triangulaiton
Authors:	Kolingerová, I.
Citation:	Journal of WSCG. 1998, vol. 6, no. 1-3.
Issue Date:	1998
Publisher:	Václav Skala - UNION Agency
Document type:	článek article
URI:	http://wscg.zcu.cz/wscg1998/wscg98.htm http://hdl.handle.net/11025/15935
ISSN:	1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online)
Keywords:	výpočetní geometrie;počítačová grafika;triangulace minimální hmotnosti;genetický algoritmus;optimalizace
Keywords in different language:	computational geometry;computer graphics;minimum weight triangulation;genetic algorithm;optimalization
Abstract in different language:	The weight of a triangulation is the sum of the Euclidean lengths of its edges. A minimum weight triangulation is such a triangulation which minimizes the weight among all triangulations of the given point set. Finding the MWT is difficult as for general data sets, no exact polynomial algorithm is known. This paper desricbes how to find an approximate solution to the MWT by a genetic approach, i.e., by a probabilistic method which maintains a set of potential solutions and tries to improve them so that at the end at least one triangulation is close or equal to the optimum. The operators used for improvement are quite general and were derived from genetics. The results obtained by this approach are compared either with optima if available or with results of already existing heuristic algorithms.
Rights:	© Václav Skala - UNION Agency
Appears in Collections:	Volume 6, number 1-3 (1998)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.