Open AccessAbout Some Localization Problems in Delaunay Triangulations
Author(s) -
Natalia Dyshkant
Publication year - 2015
Publication title -
modelirovanie i analiz informacionnyh sistem
Language(s) - English
Resource type - Journals
eISSN - 2313-5417
pISSN - 1818-1015
DOI - 10.18255/1818-1015-2012-6-112-126
Subject(s) - delaunay triangulation , bowyer–watson algorithm , constrained delaunay triangulation , pitteway triangulation , chew's second algorithm , point set triangulation , computational geometry , mathematics , triangulation , euclidean minimum spanning tree , euclidean geometry , ruppert's algorithm , surface triangulation , voronoi diagram , minimum weight triangulation , computational complexity theory , computer science , set (abstract data type) , combinatorics , algorithm , spanning tree , geometry , kruskal's algorithm , programming language
We study some problems of nodes localization in a Delaunay triangulation and problem-solving procedures. For the problem of the set of nodes the computationally efficient approach that uses Euclidean minimum spanning tree of Delaunay triangulation is proposed. Efficient estimations for computational comlexity of the proposed methods in the average and in the worst cases are proved. computational geometry, geometric search, Delaunay triangulation, merging of overlapping triangulations, unregular discrete mesh, computational complexity