Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
184 Г л. 4. Выпуклые оболочки: расширения и приложения
сделать ряд предположений о законе распределения исходных точек. Ответ на этот вопрос лежит в области стохастической геометрии, изучающей свойства случайных геометрических объектов и являющейся основой для анализа работы алгоритмов в среднем '). Нам, конечно, хотелось бы сказать: «Даны N точек, равномерно распределенные на плоскости...», — но технические проблемы делают это невозможным, так как точки могут быть равномерно распределены лишь в множестве с конечной мерой Лебега [Kendall, Moran (1963) ]2), так что мы вынуждены определить конкретную область, из которой выбираются точки. К счастью, задаче вычисления E(h) было уделено значительное внимание в литературе по статистике, и ниже приведен ряд теорем, которые имеют прямое отношение к анализу некоторых геометрических алгоритмов.
Теорема 4.1 [Renyi, Sulanke (1963)]. Если N точек выбираются равномерно и независимо из выпуклого r-угольника на плоскости, то при N оо
E(h) = (^)(y + loSeN) + 0(l), (4.1)
где у — константа Эйлера.
Теорема 4.2 [Raynaud (1970)]. Если N точек выбираются равномерно и независимо из внутренности k-мерной гиперсферы, то при N -> оо математическое ожидание E(f) гиперграней выпуклой оболочки этих точек асимптотически стремится к
?(/) = 0(/V(*-1'/(ft+1»). (4.2)
Отсюда следует, что
E(h) — 0(N113) для N точек, равномерно выбранных из круга, и
Е (И) = О (N1/2) для N точек, равномерно выбранных из сферы.
Теорема 4.3 [Raynaud (1970)]. Если N точек выбраны независимо в соответствии с k-мерным нормальным распределением, то при N оо Е(п) асимптотически стремится к
Е (h) = О ((log ЫУк-Щ, (4.3)
Теорема 4.4 [Bentley, Kung, Schkolnick, Thompson (1978)]. Если координаты N точек в k-мерном пространстве выбраны не-
') Довольно исчерпывающую информацию о результатах в этой области можно найти в книге [Santalo (1976)].
2) Речь идет об ограниченных множествах точек. — Прим. перев.
4.1. Расширения и варианты
зависимо в соответствии с произвольным непрерывным распределением (возможно, для каждой координаты используется свое распределение), то
E(h) = 0((\ogN)k~'). (4.4)
Условиям этой теоремы удовлетворяют многие распределения, включая равномерное распределение в гиперкубе.
Такое качественно неожиданное поведение выпуклых оболочек случайных множеств точек можно интуитивно объяснить следующим образом: при равномерной выборке из произвольной ограниченной области F оболочка случайного множества точек стремится принять форму границы F. В случае многоугольника накопление точек в «углах» приводит к тому, что результирующая выпуклая оболочка имеет очень мало вершин. Так как у круга нет углов, то ожидаемое число вершин выпуклой оболочки сравнительно велико, хотя, как нам известно, нет элементарного объяснения зависимости N]/3 для плоского случая1).
Из приведенных результатов непосредственно следует, что сложность в среднем алгоритма Джарвиса имеет значения, представленные в табл. I.
Таблица I. Сложность в среднем алгоритма Джарвиса
РасПРедеЛеНие
Сложность в среднем
Равномерное в выпуклом много-
угольнике
О (NlogN)
Равномерное в круге
О (N4'3)
Нормальное на плоскости
О (N (\ogN)il2)
Заметим: можно ожидать, что при нормальном распределении точек алгоритм Джарвиса потребует несколько меньше времени, чем алгоритм Грэхема2).
Все распределения, рассмотренные в этом разделе, обладают следующим свойством: математическое ожидание числа крайних точек выборки объемом N равно 0(NP), где р< 1 — некоторая константа. Такие распределения называются N"-распределениями.
Обратимся вновь к описанному в разд. 3.3.5 алгоритму «разделяй и властвуй» для плоского случая. Как уже было пока-
') Математическое ожидание числа вершин выпуклой оболочки множества из N точек можно записать как интеграл от N-n степени интеграла плотности вероятности [Efron (1965)]. Но интерес представляет не значение этой величины, а ее асимптотическое поведение в зависимости от N.
2) Двумерное нормальное распределение часто используется в качестве модели распределения попаданий Пуль в цель.
186 Гл. 4. Выпуклые оболочки: расширения и приложения
зано, этот алгоритм имеет оптимальную сложность в худшем случае. Бентли и Шеймос [Bentley, Shamos (1978)] показали, что с небольшими изменениями в реализации этот алгоритм достигает линейной оценки сложности в среднем, и, по-видимому, имеется возможность его обобщения на случай пространств более высокой размерности. Для пользы дела коротко напомним идею алгоритма. Если число заданных точек N меньше некоторой константы NQ, то оболочка вычисляется некоторым прямым методом. Если же N больше N0, то процедура сначала произвольным образом разбивает множество из N точек на два под множества, содержащие примерно по N/2 точек каждое. Затем рекурсивно ищутся выпуклые оболочки для этих двух подмножеств, т. е. решаются две подзадачи, аналогичные исходной. Результатом каждого из этих рекурсивных обращений к процедуре является выпуклый многоугольник. Оболочка исходного множества есть не что иное, как оболочка объединения оболочек подмножеств. Последняя может быть найдена за время, пропорциональное полному числу вершин обеих подоболочек.
