Root / CYBERNETICS AND PHYSICS / Volume 14, 2025, Number 4 / The planar triangulation with noisy data: the dynamic changing the order of points

The planar triangulation with noisy data: the dynamic changing the order of points

Boris Melnikov, Bowen Liu, Dang Van Vinh

We continue to consider triangulation algorithms. To the subject areas in which triangulation is used, we can add, for example, the task of clustering sensor data by location (spatial clustering) is to group data points located in the same region based on their density. The goal is to identify clusters that are close to each other. In the previous paper, the aspects related to the possible parallelization of the heuristic algorithms proposed by us were mostly considered. The main purpose of this paper is different: the main heuristic considered here is to improve the already obtained preliminary location of a certain point in the “bad case”, i.e., when we obtain from further calculations, that such an arrangement is unsuccessful; this is backtracking. We provide a general description of the triangulation algorithm we use. However, the algorithms we are considering are not limited to one description of backtracking. We use several options for choosing the next point to consider: either we take an arbitrary one (usually the next in number), or the one closest to the geometric center of the points already located, or the one furthest from this center. A simple example of such an algorithm is given. However, the main ideas of backtracking are noticeable in such a small example. Since we need to consider a wide variety of noise variants superimposed on the geometric arrangement of points, we, as in previous publications, consider geometric distances and multiply them by another implementation of independent identically distributed random variables with a mathematical expectation equal to 1 and different variants of the standard deviation. These standard deviation variants in our constructions vary from 0 (so-called geometric version) to 0.14. The end of the paper is devoted to a description of the experimental results and their understanding.
CYBERNETICS AND PHYSICS, VOL. 14, NO. 4, 2025, 356–362
https://doi.org/10.35470/2226-4116-2025-14-4-356-362

File: download