Charged balls method for solving some computational geometry problems

Abstract

Концепция замены исходной стационарной оптимизационной задачи некоторой нестационарной механической системой, стремящейся с течением времени к положению равновесия, совпадающему с решением исходной задачи, позволяет строить эффективные численные алгоритмы. Сначала составляются дифференциальные уравнения движения, затем переходом к разностной схеме их решения описывается итерационный алгоритм. Методы, получаемые указанным способом, называют методами установления. Одним из наиболее известных представителей этого класса является метод тяжелого шарика. В такие алгоритмы, как правило, входят параметры, за счет выбора которых можно существенно влиять на скорость сходимости.В настоящей заметке предлагается и исследуется представитель данного класса - метод заряженных шариков. Он является новым, эффективным оптимизационным методом, позволяющим решать некоторые задачи вычислительной геометрии. В работе подробно рассматривается задача ортогонального проектирования точки на выпуклое замкнутое множество с гладкой границей, а также задача поиска минимального расстояния между двумя такими множествами. Доказываются теоремы сходимости, получаются оценки для скорости сходимости. В заключении приводятся численные примеры, иллюстрирующие работу предложенных алгоритмов. Библиогр. 8 назв. Табл. 2.