Re: Выпуклая оболочка

From

Nick Kovaliov ()

To

Valentin Davydov

Date

2002-11-19T13:14:31Z

Area

RU.ALGORITHMS

From: "Nick Kovaliov" <Nick@urm.ru>

    > Задано множество точек внутри 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)