Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Td (N) < 2Td (N/2) + О (N (log N)d~3) + О (N), и, следовательно,
Td(N) = 0(N (log N)d~2), d>2. (4.10)
С учетом времени, затрачиваемого на предварительную сортировку, получаем следующую теорему:
') Соответствующее доказательство приведено в работе [Kung, Luccio, Preparata (1975)].
202 Гл. 4. Выпуклые оболочки: расширения и приложения
Теорема 4.9. Максимумы множеств из N точек в Ed (d ^ 2) могут быть найдены за время О (N(\og N) d~2) + О (N log N).
Этот замечательный успех метода «разделяй и властвуй», потерпевшего неудачу в решении задачи о выпуклой оболочке для d > 3 (см. разд. 3.4), является ключом к объяснению глубоких различий между двумя задачами. Ключевое в этом вопросе понятие тесно связано, но не в полной мере совпадает с понятием «декомпозируемое™», введенным Бентли [Bentley (1979)]. Более конкретно, давайте рассмотрим задачи поиска (см. гл. 2), связанные с задачами о максимумах и выпуклой оболочке, т. е. задачи «проверка на максимум» и «принадлежность выпуклой оболочке» соответственно. Предположим, множество точек S
Рис. 4.7. Точка р находится вне conv(Si) и conv(S2), но внутри выпуклой оболочки их объединения.
произвольным образом разбито на части {Si, S2}. Вопрос «Является ли р максимумом множества S(J{p}?>> имеет положительный ответ тогда и только тогда, когда получены положительные ответы на вопросы «Является ли р максимумом множества Si U {р}?» и «Является ли р максимумом множества S2 U {/>}?»• Однако нетрудно разбить S на части таким образом, что ответ на вопрос «Находится ли р вне выпуклой оболочки множества S?» является отрицательным, в то время как оба вопроса «Находится ли р вне выпуклой оболочки множества Si?» и «Находится ли р вне выпуклой оболочки S2?» имеют положительные ответы (рис. 4.7).
Прежде чем завершить этот раздел, рассмотрим работу обсуждавшегося алгоритма в среднем случае при довольно общем предположении о распределении вероятностей. Необходимый нам для этого результат дает следующая
Теорема 4.10 [Bentley, Kung, Schkolnick, Thompson (1978)]. Среднее число максимумов \i(N, d) множества S из N точек в Ей равно
H(N, d) = 0((logN)d-i) (4.11)
при условии, что координаты каждой точки независимы и выбираются из одного и того же непрерывного распределения.
4.1. Расширения и варианты
Заметим, что при используемом в алгоритме МАКСИМУ-МЫ2 способе разбиения множества на части сохраняется случайность распределения точек в каждой из частей, так как точки в обеих частях подчинены тому же самому закону распределения. Кроме того, разбиение множества можно выполнить за постоянное время, используя для этого стратегию «передачи указателя», рассмотренную в общих чертах в разд. 4.1.1. С учетом сказанного при анализе среднего случая соотношение (4.8) заменяется следующим соотношением:
E[Td(N)]^2E[Td(N/2)] + E[Fd_l(mu от,)]+ 0(1), (4.12)
где от, и m2— мощности множеств максимумов множеств Si и S2, являющихся теперь случайными величинами со средним значением \i(N/2, d). Из предыдущего обсуждения имеем
Fd-\ (mi, пи) < К\ (от, + пи) log от, (log от/-4,
где К\ — некоторая константа.
Так как т.\ и от2 ограничены сверху значением N/2, то
^-i (ти пи) < Кх (т, + пи) (log N)d~\
и, следовательно,
Е [Fd.x (от,, пи)] </С, (log N)d-3 (Е [от,] + Е [пи]) =
= /C,(logyV)d-32(i(4- d) =
= О ((log Nf-z log (Л^"1) = О ((log N?*-*).
Подставляя это значение в (4.12), получаем следующий результат:
Теорема 4.11. В предположении, что координаты каждой точки независимы и подчинены одному и тому же непрерывному закону распределения, максимумы множества из N точек в Ed могут быть найдены за время, равное в среднем
E[Td(N)] = 0(N). (4.13)
4.1.4. Выпуклая оболочка простого многоугольника
Всякий раз, когда на исследуемую задачу накладывается некоторое ограничение, множество рассматриваемых ее индивидуальных экземпляров, как правило, сокращается. В таких случаях наибольший интерес вызывает вопрос, позволит ли это ограничение разработать специально для этого случая существенно более простой метод по сравнению с общим. Конечно, не всегда удается дать убедительный ответ на этот вопрос, разработав более простой алгоритм или установив нижнюю
204
Гл. 4. Выпуклые оболочки: расширения и приложения
оценку сложности решения задачи, аналогичную нижней оценке для общего случая. Но во всех случаях исследование этого вопроса заслуживает внимания.
Примером такой «ситуации с ограничением» является задача о выпуклой оболочке простого многоугольника. Заметим, что если имеется множество S из N точек, то его всегда можно рассматривать как многоугольник, упорядочив произвольным образом точки множества и предположив, что между соседними (с учетом цикличности) точками получившейся последовательности имеется ребро. Однако в общем случае получившийся многоугольник не будет простым, т. е. некоторые его ребра могут пересекаться. Но что произойдет, если нам известно, что этот многоугольник простой? (Определение простого многоугольника см. в разд. 1.3.)
