Charged ball method for solving some computational geometry problems

Research output

2 Citations (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.

Original languageEnglish
Pages (from-to)209-216
Number of pages8
JournalVestnik St. Petersburg University: Mathematics
Issue number3
Publication statusPublished - 1 Jul 2017

Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Charged ball method for solving some computational geometry problems'. Together they form a unique fingerprint.

Cite this