Two Related Problems of Redundancy Reduction in Data Representation by Means of Convex Polyhedra
- Авторлар: Bedrintsev A.1, Chepyzhov V.1
-
Мекемелер:
- Kharkevich Institute for Information Transmission Problems
- Шығарылым: Том 62, № 12 (2017)
- Беттер: 1456-1463
- Бөлім: Mathematical Models and Computational Methods
- URL: https://journals.rcsi.science/1064-2269/article/view/199095
- DOI: https://doi.org/10.1134/S106422691712004X
- ID: 199095
Дәйексөз келтіру
Аннотация
Two problems of data representation by means of convex polyhedra are considered. In the first problem, it is required to exclude from a finite set of points X the points that are not vertices of the convex hull of X. An algorithm based on solving a series of linear programming problems is developed. Its computational complexity is asymptotically lower than the complexity of a convex hull constructing, and it requires much less additional memory than for constructing a convex hull. The second problem consists in finding the minimal subset of inequalities in a system of linear inequalities whose solution set coincides with the solution set of the initial system. It is shown that this problem can be solved similarly to the first one, and the solution algorithm can be extended to the case of nonlinear inequalities. Randomized improved versions of both algorithms are proposed.
Авторлар туралы
A. Bedrintsev
Kharkevich Institute for Information Transmission Problems
Хат алмасуға жауапты Автор.
Email: alekseybed@phystech.edu
Ресей, Moscow, 127994
V. Chepyzhov
Kharkevich Institute for Information Transmission Problems
Email: alekseybed@phystech.edu
Ресей, Moscow, 127994