Charged ball method for solving some computational geometry problems

Результат исследований: Научные публикации в периодических изданияхстатья

2 Цитирования (Scopus)


The concept of replacement of the initial stationary optimization problem with some nonstationary mechanical system tending with time to the position of equilibrium, which coincides with the solution of the initial problem, makes it possible to construct effective numerical algorithms. First, differential equations of the movement should be derived. Then we pass to the difference scheme and define the iteration algorithm. There is a wide class of optimization methods constructed in such a way. One of the most known representatives of this class is the heavy ball method. As a rule, such type of algorithms includes parameters that highly affect the convergence rate. In this paper, the charged ball method, belonging to this class, is proposed and investigated. It is a new effective optimization method that allows solving some computational geometry problems. A problem of orthogonal projection of a point onto a convex closed set with a smooth boundary and the problem of finding the minimum distance between two such sets are considered in detail. The convergence theorems are proved, and the estimates for the convergence rate are found. Numerical examples illustrating the work of the proposed algorithms are given.

Язык оригиналаанглийский
Страницы (с-по)209-216
Число страниц8
ЖурналVestnik St. Petersburg University: Mathematics
Номер выпуска3
СостояниеОпубликовано - 1 июл 2017

Предметные области Scopus

  • Математика (все)

Fingerprint Подробные сведения о темах исследования «Charged ball method for solving some computational geometry problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).