Abstract:
The problem of polyhedral approximation of a multidimensional ball is considered. It is well known that the norm of the ff-vector (the maximum number of faces of all dimensions) of an approximating polytope grows at least as fast as O(δ(1−d)/2)O(δ(1−d)/2), where δδ is the Hausdorff deviation and d is the space dimension. An iterative method, namely, the deep holes method is used to construct metric nets. As applied to the problem under study, the method sequentially supplements the vertex set of the polytope with its deep holes in the metric on the ball surface (i.e., with points of the surface that are farthest away from the vertices of the polytope). It is shown that the facet structure cardinality of the constructed polytope has an optimal growth rate. It is also shown that the number of faces of all dimensions in the approximating polytopes generated by the method is asymptotically proportional to the number of their vertices. Closed-form expressions for the constants are obtained, which depend only on the dimension of the space, including the case of high dimensions. For low dimensions (dd ranging from 33 to 55), upper bounds for the growth rate of the number of faces of all dimensions are obtained depending on the accuracy of the approximation.
Key words:
convex bodies, multidimensional ball, polyhedral approximation, coverings and packings on the sphere, sphere packing in a ball, spherical codes, polyhedral approximation methods, vertices, facets, faces, facet structure, ff-vector.
Citation:
G. K. Kamenev, “Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality”, Zh. Vychisl. Mat. Mat. Fiz., 54:8 (2014), 1235–1248; Comput. Math. Math. Phys., 54:8 (2014), 1201–1213
\Bibitem{Kam14}
\by G.~K.~Kamenev
\paper Method for polyhedral approximation of a ball with an optimal order of growth of the facet structure cardinality
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2014
\vol 54
\issue 8
\pages 1235--1248
\mathnet{http://mi.mathnet.ru/zvmmf10071}
\crossref{https://doi.org/10.7868/S0044466914080067}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3250870}
\zmath{https://zbmath.org/?q=an:06391163}
\elib{https://elibrary.ru/item.asp?id=21803833}
\transl
\jour Comput. Math. Math. Phys.
\yr 2014
\vol 54
\issue 8
\pages 1201--1213
\crossref{https://doi.org/10.1134/S0965542514080053}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000341085500001}
\elib{https://elibrary.ru/item.asp?id=23990207}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84907334492}
Linking options:
https://www.mathnet.ru/eng/zvmmf10071
https://www.mathnet.ru/eng/zvmmf/v54/i8/p1235
This publication is cited in the following 10 articles:
Daniela Lera, Maria Chiara Nasso, Mikhail Posypkin, Yaroslav D. Sergeyev, “Determining solution set of nonlinear inequalities using space-filling curves for finding working spaces of planar robots”, J Glob Optim, 2024
Lera D. Posypkin M. Sergeyev Ya.D., “Space-Filling Curves For Numerical Approximation and Visualization of Solutions to Systems of Nonlinear Inequalities With Applications in Robotics”, Appl. Math. Comput., 390 (2021), 125660
R. V. Efremov, “Complexity of methods for approximating convex compact bodies by double description polytopes and complexity bounds for a hyperball”, Comput. Math. Math. Phys., 59:7 (2019), 1204–1213
E V Gaponenko, D I Malyshev, L Behera, “Approximation of the parallel robot working area using the method of nonuniform covering”, J. Phys.: Conf. Ser., 1333:5 (2019), 052005
George K. Kamenev, Lecture Notes in Computational Science and Engineering, 131, Numerical Geometry, Grid Generation and Scientific Computing, 2019, 157
L. A. Rybak, E. V. Gaponenko, D. I. Malyshev, Mechanisms and Machine Science, 73, Advances in Mechanism and Machine Science, 2019, 741
Yu. Evtushenko, M. Posypkin, L. Rybak, A. Turkin, “Approximating a solution set of nonlinear inequalities”, J. Glob. Optim., 71:1, SI (2018), 129–145
Yu. G. Evtushenko, M. A. Posypkin, L. A. Rybak, A. V. Turkin, “Finding sets of solutions to systems of nonlinear inequalities”, Comput. Math. Math. Phys., 57:8 (2017), 1241–1247
G. K. Kamenev, “Efficiency of the estimate refinement method for polyhedral approximation of multidimensional balls”, Comput. Math. Math. Phys., 56:5 (2016), 744–755
G. K. Kamenev, “Asymptotic properties of the estimate refinement method in polyhedral approximation of multidimensional balls”, Comput. Math. Math. Phys., 55:10 (2015), 1619–1632
Citation in format AMSBIB
Contact us: