Аннотация:
Пусть два выпуклых компакта в R^n, А и В, заданы своими опорными функциями. Рассматривается задача поиска такого минимального коэффициента гомотетии t, что множество tB может покрыть А после некоторого сдвига. Известный метод решения этой задачи сходится за разумное время в размерностях не выше 4. Мы предлагаем два алгоритма, эффективно решающих эту задачу. Первый алгоритм организует поиск точек, в которых внутренний компакт "упирается" во внешний компакт, постепенно уменьшая пространство поиска. Второй алгоритм использует градиентный метод и дает хорошие результаты даже в размерности 100, но требует дополнительных ограничений на множества А и В.
|
