ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Nick Kovaliov                        2:5020/400     19 Nov 2002  14:14:31
 To : Valentin Davydov
 Subject : Re: Выпуклая оболочка
 -------------------------------------------------------------------------------- 
 

     > Задано множество точек внутри K-мерного куба.
     > Требуется построить выпуклый многогранник
     > минимального объёма, который, во-первых,
     > содержал бы все эти точки, во-вторых,
     > целиком лежал бы внутри куба, и в-третьих,
     > число вершин которого не превосходило бы
     > заранее заданного N.
     > Как бы к решению подступиться?
 
 Третье условие сложное ...
 
     > Для существования решения
     > можно считать, что N >= 2^K.
     > Годится также и субоптимальное решение
     > (то есть объём, близкий к минимальному,
     > если степень близости легко оценить).
 
 А обычные методы построения выпуклой оболочки,
 обобщённые на K-мерный случай пойдут ? ...
 Метод заворачивания подарка ? ...
 Метод Джарвиса ? ...
 
 http://graphics.cs.msu.su/courses/cg_el99/notes/lect10.doc
 http://graphics.cs.msu.su/courses/cg_el99/notes/
 
 А вот насчёт "в третьих",
 если это и правда важно, но не знаааю ...
 
 Построить выпуклую оболочку,
 а потом как-то постепенно убивать
 из неё плоскости ...
 
     > P.S. Метрика - обычная эвклидова.
 
 Метрика тут не причём.
 
 До встречи, всего наилучшего !
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Выпуклая оболочка   Valentin Davydov   19 Nov 2002 10:31:16   Re: Выпуклая оболочка   Nick Kovaliov   19 Nov 2002 14:14:31   Выпуклая оболочка   Vovanius Uryvaeff   19 Nov 2002 19:54:53   Выпуклая оболочка   €«мп Љ ­в®а   19 Nov 2002 21:04:54