V. Tereshchenko

Authors: V. Tereshchenko, D. Taran

Abstract:

In this paper we propose a new approach to constructing the Delaunay Triangulation and the optimum algorithm for the case of multidimensional spaces (d ≥ 2). Analysing the modern state, it is possible to draw a conclusion, that the ideas for the existing effective algorithms developed for the case of d ≥ 2 are not simple to generalize on a multidimensional case, without the loss of efficiency. We offer for the solving this problem an effective algorithm that satisfies all the given requirements. But theoretical complexity of the problem it is impossible to improve as the Worst - Case Optimality for algorithms of solving such a problem is proved.

Keywords: delaunay triangulation, optimal algorithm, Voronoi diagram, multidimensional space

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1660

Authors: V. Tereshchenko, A. Tregubenko

Abstract:

In this study we survey the method for fast finding a minimum link path between two arbitrary points within a simple polygon, which can pass only through the vertices, with preprocessing.

Keywords: Minimum link path, simple polygon, Steiner points, optimal algorithm

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1221

Authors: V. Tereshchenko, V. Muravitskiy

Abstract:

We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple polygonalizations of a fixed set of points and finds the minimal area polygon, in O (n3) time and using O(n2) memory.

Keywords: approximate algorithm, simple polygon, minimal area polygon, polygonalizations

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1889