|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Valentin Davydov 2:5020/400 19 Nov 2002 10:31:16
To : All
Subject : Выпуклая оболочка
--------------------------------------------------------------------------------
Задано множество точек внутри K-мерного куба. Требуется построить
выпуклый многогранник минимального объёма, который, во-первых,
содержал бы все эти точки, во-вторых, целиком лежал бы внутри куба,
и в-третьих, число вершин которого не превосходило бы заранее
заданного N. Как бы к решению подступиться?
Для существования решения можно считать, что N >= 2^K. Годится также
и субоптимальное решение (то есть объём, близкий к минимальному,
если степень близости легко оценить).
Вал. Дав.
P.S. Метрика - обычная эвклидова.
--- ifmail v.2.15dev5
* Origin: St. Petersburg State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
