Finite approximation methods for two-dimensional sets and their application to geometric optimization problems


Cite item

Full Text

Abstract

This study investigates the problem of approximating closed bounded sets in two-dimensional real space by finite subsets with a given accuracy in the Hausdorff metric. The main focus is on developing an effective approximation method for the class of sets defined by stepwise systems of inequalities.
The proposed method is based on constructing special grid structures that allow controlling the approximation accuracy through a parameter $\tau > 0$. Corresponding theoretical statements about the properties of such approximations are proved.
The problem of finding an optimal piecewise-linear path between two points with a single turn under angle constraints is examined in detail. The developed methods are applicable for solving various geometric optimization problems.

About the authors

Victor N. Nefedov

Moscow Aviation Institute (National Research University)

Email: nefedovvn54@yandex.ru
ORCID iD: 0000-0001-6053-2066
Scopus Author ID: 7103271245
ResearcherId: S-2650-2019
https://www.mathnet.ru/person63464

Cand. Phys. & Math. Sci., Associate Professor; Associate Professor; Dept. of Mathematical Cybernetics1

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

Fedor V. Svoykin

Saint Petersburg State Forest Technical University under name of S. M. Kirov

Email: svoykin_fv@mail.ru
ORCID iD: 0000-0002-8507-9584
SPIN-code: 8938-6910
Scopus Author ID: 57217847423
ResearcherId: AAC-4074-2020
https://www.mathnet.ru/person228056

Cand. Techn. Sci., Associate Professor; Associate Professor; Dept. of Forestry Technology2

Russian Federation, 194021, Saint Petersburg, Institutskiy per., 5

Boris A. Garibyan

Moscow Aviation Institute (National Research University)

Email: bagarib@yandex.ru
ORCID iD: 0000-0001-8309-3086
SPIN-code: 8622-4854
Scopus Author ID: 57202449216
ResearcherId: Y-6983-2018
https://www.mathnet.ru/person228057

Cand. Phys. & Math. Sci., Associate Professor; Associate Professor; Dept. of Mathematical Cybernetics1

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

Anatoliy V. Ryapukhin

Moscow Aviation Institute (National Research University)

Author for correspondence.
Email: anatoliiruapukhin@yandex.ru
ORCID iD: 0000-0002-2208-6875
SPIN-code: 6693-0850
Scopus Author ID: 57211373896
ResearcherId: ABB-3999-2020
https://www.mathnet.ru/person145977

Senior Lecturer; Dept. of Design and Certification of Aviation Equipment1

Russian Federation, 125993, Moscow, Volokolamskoe Shosse, 4

Nikolay S. Korolko

Saint Petersburg State Forest Technical University under name of S. M. Kirov

Email: kns89lta@mail.ru
ORCID iD: 0009-0009-6289-2984
SPIN-code: 6309-8365
Scopus Author ID: 57220187617
https://www.mathnet.ru/person228087

Postgraduate Research Student; Dept. of Forestry Technology2

Russian Federation, 194021, Saint Petersburg, Institutskiy per., 5

References

  1. Vasil’ev F. P. Chislennye metody resheniia ekstremal’nykh zadach [Numerical Methods for Solving of Extremal Problems]. Moscow, Nauka, 1988, 550 pp. (In Russian). EDN: UTKWUO.
  2. Nesterov Yu. E. Vvedenie v vypukluiu optimizatsiiu [Introduction to Convex Optimization]. Moscow, Moscow Center for Continuous Mathematical Education, 2010, 280 pp. (In Russian). EDN: SDSFYV.
  3. Nefedov V. N. Some problems of solving Lipschitzian global optimization problems using the branch and bound method, Comput. Math. Math. Phys., 1992, vol. 32, no. 4, pp. 433–445. EDN: XKQMEC.
  4. Evtushenko Yu. G. Numerical methods for finding global extrema (Case of a non-uniform mesh), U.S.S.R. Comput. Math. Math. Phys., 1971, vol. 11, no. 6, pp. 38–54. EDN: XOYJSF. DOI: https://doi.org/10.1016/0041-5553(71)90065-6.
  5. Leonov V. V. The method of coverings for seeking a global maximum of a function of several variables, In: Issledovanie po kibernetike [Research in Cybernetics]. Moscow, Sov. Radio, 1970, pp. 41–52 (In Russian).
  6. Piyavskii S. A. An algorithm for finding the absolute extremum of a function, U.S.S.R. Comput. Math. Math. Phys., 1972, vol. 12, no. 4, pp. 57–67. EDN: TTTJWV. DOI: https://doi.org/10.1016/0041-5553(72)90115-2.
  7. Potapov M. A. Methods of non-uniform coverings and their application for solving problems of global optimization in a dialogue mode, Diss. Cand. Phys. Math. Sci. Moscow, 1984, 104 pp. (In Russian). EDN: NPAFWT.
  8. Nefedov V. N. On a method of global maximization of a function of several variables on a rectangular prism, Dep. in VINITI, 1.06.85, no. 377-85 DEP. Moscow, 1985 (In Russian).
  9. Evtushenko Yu. G., Rat’kin V. A. The method of half-divisions for global optimization of a function of many variables, Sov. J. Comput. Syst. Sci., 1987, vol. 25, no. 5, pp. 75–84.
  10. Nefedov V. N. The search for a global maximum of a function of several variables in a set specified by constraints of the inequality type, U.S.S.R. Comput. Math. Math. Phys., 1987, vol. 27, no. 1, pp. 23–32. DOI: https://doi.org/10.1016/0041-5553(87)90114-5.
  11. Ishenko A. V., Kireev I. V. The algorithm for generation of two-dimensional embedded grids, J. Sib. Fed. Univ. Math. Phys., 2009, vol. 2, no. 1, pp. 83–90 (In Russian). EDN: JWKGRP.
  12. Nefedov V. N. Approximation of a Pareto set, U.S.S.R. Comput. Math. Math. Phys., 1984, vol. 24, no. 4, pp. 19–28. DOI: https://doi.org/10.1016/0041-5553(84)90225-8.
  13. Nefedov V. N. Approximation of a set of Pareto-optimal solutions, U.S.S.R. Comput. Math. Math. Phys., 1986, vol. 26, no. 1, pp. 99–107. DOI: https://doi.org/https://doi.org/10.1016/0041-5553(86)90192-8.
  14. Hausdorff F. Set Theory. New York, Dover Publ., 1944, 307 pp.
  15. Skvortsov V. A. Primery metricheskikh prostranstv [Examples of Metric Spaces], Matematicheskoe Prosveshchenie, vol. 16. Moscow, Moscow Center for Continuous Mathematical Education, 2012, 27 pp. (In Russian). EDN: QJZGML.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Figure 1. Selection of elements belonging to $\boldsymbol S^{\tau}$

Download (70KB)
Indexing metadata
3. Figure 2. Relative positions of the points $C$, $C_\alpha$, and $C_{\alpha_0}$

Download (29KB)
Indexing metadata
4. Figure 3. The point $C \in \check{\Gamma}_\varphi$

Download (44KB)
Indexing metadata
5. Figure 4. The point $C (\operatorname{tg} \tfrac \varphi 2, 0) \in \check{\Gamma}_\varphi$

Download (51KB)
Indexing metadata

Copyright (c) 2025 Authors; Samara State Technical University (Compilation, Design, and Layout)

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».