метод случайного поиска для построения выпуклой оболочки

[sadomovalex]

добрый день всем
ситуация следующая: моей знакомой преподаватель задал тему - Алгоритм построения выпуклой оболочки множества точек методом случайного поиска. Здесь я спросил про литературу по выпуклым оболочкам в $n$-мерном пространстве. Но, как выяснилось, этот метод придумал сам преподаватель, т.е. описания его нигде нет. Единственно, что есть на данный момент - это небольшое описание его со слов преподавателя: http://www.box.net/shared/ke1cr70fx9. Записано абы как, т.к. преподаватель не стал объяснять и проверять записанное, т.е. там есть ошибки. Я не исключаю также, что метод сам по себе может быть ошибычным. Вообщем надеюсь с вашей общей помощью разобраться в хотя бы в суте метода и по ходу составить вопросы преподавателю. Думаю, что будет проще рассматривать двумерный случай, как частный случай, и если там окажутся какие-нибудь противоречия, можно будет сделать вывод, что метод неправильный.

Итак, ставится задача отыскаяния выпуклой оболочки для конечного множества $M$ точек $n$-мерного евклидового пространства: $M=(x_1, x_2,\ldots x_N)\subseteq E^n,x_i=(x_{i_1},x_{i_2},\ldots x_{i_n})$ (заметим, что здесь первое отличие - в файле в самом начале описания самого алгоритма рассматривается $E^d$ и $\dim M=d$, но далее все векторы имеют $n$ координат). Все гиперплоскости (отрезок при $n=2$, плоскость при $n=3$), являющиеся гранями искомой выпуклой оболочки предлагается искать в виде $(a,x)=1$, где $a$ - какой-либо вектор в $n$-мерном пространстве.
Перед началом множество $M$ преобразовывают с помощью параллельного переноса таким образом, чтобы его центр тяжести лежал в начале координат: $x^*=\displaystyle\frac{x_1+x_2+\ldots+x_N}{N},x_i\rightarrow x_i-x^*$.

Шаг 1.
Выбираем случайное направление: генерируем $n$ случайных независимых величин, распределенных по нормальному закону с параметрами $m_x=0,D_x=1$: $a_1,a_2,\ldots a_n,r=\sqrt{a_1^2+a_2^2+\ldots+a_n^2}$ и определяем нормированный вектор $a=(\frac{a_1}{r},\frac{a_2}{r},\ldots \frac{a_n}{r})$ - случайное направление в $E^n$. Затем вычисляем всевозможные скалярные произведения $(a,x_i),i=1,\ldots n$, где $x_i$ - вектор, имеющий начало в начале координат и конец в точке $x_i$ исходного множества $M$. Из этих скалярных произведений выбирают максимальное положительное $\beta=\max(a,x_k)$. При этом почему-то утверждается, что такое $\beta$ обязательно найдется для любого случайного направления, заданного вектором $a$.
Вопрос 1. Так ли это при условии центрирования множества $M$ (т.е. когда центр тяжести лежит в начале координат)?
Далее утверждается, что уравнение 1-й гиперплоскости имеет вид $(\frac{a}{\beta},x)=1$. Конечно, если мы подставим сюда вместо вектора $x$ вектор $x_k$, то получим тождественное равенство, т.е. эта "гиперплоскость" проходит через точку $x_k$.
Вопрос 2. Но откуда следует, что она будет являться одной из искомых гиперплоскостей, являющихся границей выпуклой оболочки.

Далее шаг 2, который вообще плавает. Сначала с 1-м бы разобраться.
Приведу в конце рассуждения преподавателя, переданные в устной форме. Мы имеем множество точек. Задаем случайное направление, находим уравнение первой прямой (в двумерном случае) на шаге 1, и по нему перемещаем эту прямую до тех пор, пока не встретим точку на плоскости. Затем идут манипуляции с шага 2..

PS. Модераторам просьба не переносить тему в Computer science, т.к. на текущий момент необходимо разобраться с математической стороной вопроса.

[Brukvalub]

sadomovalex писал(а):

При этом почему-то утверждается, что такое $\beta$ обязательно найдется для любого случайного направления, заданного вектором $a$.

Вот это как раз очевидно: так как

\[\sum\limits_{i = 1}^n {\overrightarrow {x_i } } = \overrightarrow o \Rightarrow \forall \overrightarrow b \quad \sum\limits_{i = 1}^n {\overrightarrow {(x_i } } ,\overrightarrow b ) = 0\]

, то либо все слагаемые в последней сумме равны 0, что соответствует неинтересному вырожденному случаю, либо среди этих слагаемых есть положительное число , а в конечном множестве положительных чисел всегда найдется одно или несколько самых положительных

[sadomovalex]

Brukvalub писал(а):

Вот это как раз очевидно: так как

\[\sum\limits_{i = 1}^n {\overrightarrow {x_i } } = \overrightarrow o \Rightarrow \forall \overrightarrow b \quad \sum\limits_{i = 1}^n {\overrightarrow {(x_i } } ,\overrightarrow b ) = 0\]

ага, если заметить, что сумма векторов, соединяющих центр тяжести с вершинами, равен нулю. Спасибо, Brukvalub, одним вопросом меньше. Сегодня вечером дома продолжу изучение метода

[Brukvalub]

sadomovalex писал(а):

Вопрос 2. Но откуда следует, что она будет являться одной из искомых гиперплоскостей, являющихся границей выпуклой оболочки.

Это тоже очевидно, поскольку два полупространства, на которые гиперплоскость разделяет все пространство, определяются неравенствами , а, в силу условия экстремальности выбора точки на первом шаге, во всех остальных точках конечного набора будет выполняться одно и то же нестрогое неравенство, то есть все точки окажутся по одну сторону от гиперплоскости.
Как мне кажется, центральный вопрос этого алгоритма - это вопрос его остановки через конечное число шагов???

[K-3]

Все это похоже на вариации quickhull (qhull), поэтому надо, наверное, посмотреть ссылки на статьи, которые есть в упомянутой (в разделе Computer Scence) статье про qhull
http://www.qhull.org/
http://citeseer.ist.psu.edu/83502.html

[sadomovalex]

K-3
в статье по Вашей второй ссылке говорится, что

Цитата:

The convex hull of a set of points is the smallest convex set that contains the points. This paper presents a practical convex hull algorithm that combines the two-dimensional Quickhull Algorithm with the general dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and Delaunay triangulation.

и далее:

Цитата:

Recent work on convex hulls and Delaunay triangiilations has focused on variations of a randomized, incremental algorithm that has optimal expected performance [12] [15] [21] [28] [30] [37]. Points are processed one at a time in a random order. In this paper, we propose and analyze a strategy for processing points in a more efficient order. The result is a faster algorithm for distributions with interior points.

из этих источников я выделил 2, которые наиболее близки к данной теме: здесь. Если кто-нибудь имеет доступ к ним, буду очень признателен:
[28]. L. Guibas, D.E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, pages 381-413, 1992.
[37]. K. Mulmuley. Computational geometry. An introduction Throught Randomized Algorithms. Prentice-Hall, 1994.

По поводу самого алгоритма, представленного в исходном посте напишу мысли и идеи по-позже, только вот разберусь с работой

Добавлено спустя 57 минут 37 секунд:

Brukvalub
да, этот вопрос об остановке алгоритма у меня тоже появился вчера дома, когда я разбирался с ним, и его необходимо задать преподавателю.
Если в двумерном и трехмерном случае (с помощью формулы Эйлера например $v-e+f=2$) это дело скорее всего удасться как-то разрулить. То в $n$-мерном пространстве дело куда сложнее. В книге Препарата Ф., Шеймос М. — Вычислительная геометрия: введение, с. 119, в частности, указывается, что:

Цитата:

число F(d,N) гиперграней $d$-политопа с $N$-вершинами может доходить до
$F(d,N)=\left\{\begin{array}{l}\frac{2N}{d}\binom{N-\frac{d}{2}-1}{\frac{d}{2}-1}, d\mod 2 = 0&&2\binom{N-\left\lfloor\frac{d}{2}\right\rfloor-1}{\left\lfloor\frac{d}{2}\right\rfloor}, d\mod 2 = 1\end{array}\right.$

[sadomovalex]

Brukvalub писал(а):

sadomovalex писал(а):

Вопрос 2. Но откуда следует, что она будет являться одной из искомых гиперплоскостей, являющихся границей выпуклой оболочки.

Это тоже очевидно, поскольку два полупространства, на которые гиперплоскость разделяет все пространство, определяются неравенствами , а, в силу условия экстремальности выбора точки на первом шаге, во всех остальных точках конечного набора будет выполняться одно и то же нестрогое неравенство, то есть все точки окажутся по одну сторону от гиперплоскости.

не понял до конца. Рассмотрим двумерный случай для 3-х точек, расположенных в вершинах треугольника. Тогда центр координат совпадет с точкой пересечения медиан:

Допустим, что $\overline{a}$ - случайный вектор, который мы получили на шаге 1, и пусть максимум скалярного произведения достигается для $x_1$: $\beta=(\overline{a},\overline{x_1})$. Т.е. по алгоритму прямая $(\frac{\overline{a}}{\beta},\overline{x})=1$ - первая гиперплоскость, которая является границей выпуклой оболочки. Но все, что я пока про нее могу сказать, что она проходит через $x_1$ и перпендикулярна вектору $\overline{a}$, т.к. прямая вида $Ax+By+C=0$ перпендикулярна вектору $(A,B)$ и параллельная $(-B,A)$. Почему же она является границей выпуклой оболочки?
Граница выпуклой оболочки должна проходить через две точки в данном случае: $x_1$ и $x_2$ или $x_1$ и $x_3$. Кстати во 2-м шаге, до которого я пока не добрался, точки "вгоняются" в гиперплоскость, до тех пор, пока их не станет там $n$ штук, где $n$-размерность задачи. Верно ли что $n$-мерная гиперплоскость однозначно определяется $n$ точками (как например 2 точки для прямой в двумерном случае, 3 точки для плоскости для трехмерного)?

[Brukvalub]

sadomovalex писал(а):

Почему же она является границей выпуклой оболочки?

Вы правы, я неясно выразился. Я писал лишь о том, что все точки лежат по одну сторону от каждой такой гиперплоскости, поэтому пересечение бооо...оольшого числа таких гиперплоскостей и даст "в пределе" выпуклую оболочку. Но это так, "на пальцах"...

[sadomovalex]

Brukvalub писал(а):

Вы правы, я неясно выразился. Я писал лишь о том, что все точки лежат по одну сторону от каждой такой гиперплоскости, поэтому пересечение бооо...оольшого числа таких гиперплоскостей и даст "в пределе" выпуклую оболочку. Но это так, "на пальцах"...

мне пока не хватает чего-то, что помогло бы общую суть метода ухватить. Метод случайного поиска - это один из стандартных методов решения экстремальных задач. В книге Васильева Ф.П. — Методы решения экстремальных задач написано про него:

Цитата:

Наряду с описанными выше методами минимизации функций переменных существует большая группа методов поиска минимума, объединенных под названием метода случайного поиска. Метод случайного поиска, в отличие от ранее рассмотренных методов, характеризуется намеренным введением элемента случайности в алгоритм поиска. Многие варианты метода случайного поиска сводятся к построению последовательности ${u_k}$ по правилу:
$u_{k+1}=u_k+\alpha_k\xi,\,k=0,1,\ldots$
где $\alpha_k$ —некоторая положительная величина, $\xi=(\xi_1,\ldots,\xi_n)$ —
какая-либо реализация $n$-мерной случайной величины $\xi$ с известным законом распределения.

это сильно похоже на формулу из шага 2, используемую для нахождения следующей точки, которую нужно загнать в гиперплоскость:
$\overline{a}_{k+1}=\overline{a}_k+t\overline{u}$, где $\overline{u}$ - вектор, ортогональный всем найденным до этого точкам текущей гиперплоскости; $\overline{a}_k$ - на 1-м шаге это случайный вектор, на $k$-м - это вектор вычисленный по той же формуле; $t$ - положительное число, которое ищется из условия что для какой-либо еще точки из тех, что еще не принадлежат гиперплоскости, выполняется равенство $(\overline{a}_{k+1},\overline{x}_j)=(\overline{a}_k+t\overline{u},\overline{x}_j)=1$