Abstract:
A problem related to that of finding the Chebyshev center of a compact convex set in Rn is considered, namely, the problem of calculating the center and the least positive ratio of a homothety under which the image of a given compact convex set in Rn covers another given compact convex set. Both sets are defined by their support functions. A solution algorithm is proposed which consists in discretizing the support functions on a grid of unit vectors and reducing the problem to a linear programming problem. The error of the solution is estimated in terms of the distance between the given set and its approximation in the Hausdorff metric. For the stability of the approximate solution, it is essential that the sets be uniformly convex and a certain set in the dual space has a nonempty interior.
Keywords:
Chebyshev center, stability of minimization problem, Hausdorff metric, linear programming, support function.
Citation:
M. V. Balashov, “Covering a Set by a Convex Compactum: Error Estimates and Computation”, Mat. Zametki, 112:3 (2022), 337–349; Math. Notes, 112:3 (2022), 349–359
\Bibitem{Bal22}
\by M.~V.~Balashov
\paper Covering a Set by a Convex Compactum: Error Estimates and Computation
\jour Mat. Zametki
\yr 2022
\vol 112
\issue 3
\pages 337--349
\mathnet{http://mi.mathnet.ru/mzm13537}
\crossref{https://doi.org/10.4213/mzm13537}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4538770}
\transl
\jour Math. Notes
\yr 2022
\vol 112
\issue 3
\pages 349--359
\crossref{https://doi.org/10.1134/S0001434622090024}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85140582219}
Linking options:
https://www.mathnet.ru/eng/mzm13537
https://doi.org/10.4213/mzm13537
https://www.mathnet.ru/eng/mzm/v112/i3/p337
This publication is cited in the following 4 articles:
P. A. Arkhipov, “Algoritm nakhozhdeniya obobschennogo chebyshevskogo tsentra mnozhestv, zadannykh opornymi funktsiyami”, Avtomat. i telemekh., 2024, no. 6, 67–82
P. A. Arkhipov, “An Algorithm for Finding the Generalized Chebyshev Center of Sets Defined via Their Support Functions”, ARC, 85:6 (2024), 598
P. A. Arkhipov, “An Algorithm for Finding the Generalized Chebyshev Center of Sets Defined via Their Support Functions”, Autom Remote Control, 85:6 (2024), 522
M. V. Balashov, R. A. Kamalov, “Optimization of the reachable set of a linear system with respect to another set”, Comput. Math. Math. Phys., 63:5 (2023), 751–770
Citation in format AMSBIB
Contact us: