Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 53

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 47 48 49 50 51 52 < 53 > 54 55 56 57 58 59 .. 180 >> Следующая


Задача В06 (ВЫПУКЛАЯ ОБОЛОЧКА В РЕАЛЬНОМ ВРЕМЕНИ). На плоскости задана последовательность из Лоточек ри .. ., pN. Требуется найти их выпуклую оболочку при условии, что время задержки поступления точек постоянно.

Соответствующий алгоритм должен поддерживать некоторое представление текущей выпуклой оболочки и корректировать его по мере поступления точек. Вопрос состоит в том, можно ли сделать это, не принося в жертву оценку 0(N\ogN) времени выполнения алгоритма, необходимого на обработку всего множества точек.

Нет проблемы разработать открытый алгоритм построения выпуклой оболочки, если время обработки не принимается во внимание. Например, после получения каждой точки можно было бы выполнять алгоритм Грэхема, получив при этом оценку сложности 0(.W2loo;N). Можно проявить большую сообразительность, вспомнив, что алгоритм Грэхема состоит из двух отдельных шагов — сортировки и обхода.

1. Вводить точки до тех пор, пока не будут обнаружены три неколлинеарные точки. Их центроид будет внутренней точкой окончательной выпуклой оболочки и, таким образом, подходит для начала координат, относительно которого определяются полярные углы точек при сортировке в алгоритме ОБО-ЛОЧКАГРЭХЕМА.

2. Поддерживать связанный список упорядоченных крайних точек. При поступлении точки р,- временно вставить ее в этот список в соответствии с ее полярным углом, затратив на это время 0{i).

3.3. Алгоритм построения выпуклой оболочки

145

3. Выполнить просмотр связанного списка крайних точек методом Грэхема. Так как просмотр методом Грэхема является линейным, то на это потребуется лишь O(t) времени. Возможны три варианта завершения этого шага:

a) точка pi является крайней обработанного на текущий момент множества, и ее включение в число крайних точек вызывает удаление нескольких других точек;

b) точка pi является крайней, но никакие другие точки не удаляются; iUA^

c) точка pi является внутренней для создаваемой в!|итуЖлой оболочки, и поэтому она удаляется.

В каждом случае размер списка увеличивается не более чем на единицу. Полное время, затрачиваемое этим алгоритмом, в худшем случае равно 0(N2), что имеет место, если каждая новая точка оказывается крайней точкой.

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

Следуя по этому пути, Шеймос [Shamos (1978)] разработал алгоритм, который для множества из N точек выполняется глобально за время О (N log N) и, следовательно, оптимален. Но при этом на корректировку тратится время 0(\og2N). Чтобы определить, насколько этот алгоритм соответствует требованиям, предъявляемым к алгоритмам для обработки в реальном времени, заметим, что нижние оценки, полученные для закрытых алгоритмов, в равной мере применимы и к открытым алгоритмам. Этот факт можно использовать для получения нижних оценок времени, которое открытый алгоритм должен тратить на обработку очередной порции данных. Пусть Т[М) — время, используемое открытым алгоритмом в' худшем случае, при решении задачи с N элементами вводимых данных; U(i) — время, используемое на обработку между поступлением г-го и (i + 1)-го элементов данных. Если L(N) —нижняя оценка времени, достаточного для решения задачи, то из соотношения

r(N)='iu(i)>L{N) (3.9)

находим нижнюю оценку для U(i).

В нашем случае совместное использование теоремы 3.2 и соотношения (3.9) приводит к следующей теореме, устанавливающей для заданного /V нижнюю оценку для константы задержки поступления данных, упомянутой в формулировке задачи В06.

146

Гл. 3. Выпуклые оболочки: основные алгоритмы

Теорема 3.10. Любой открытый алгоритм построения выпуклой оболочки в худшем случае должен затрачивать на обработку между поступлением последовательных элементов данных время Q(log-iV).

Таким образом, можно заключить, что упомянутый выше алгоритм не удовлетворяет требованию, предъявляемому к алгоритмам реального времени. Однако впоследствии Препарата [Preparata (1979)] разработал открытый алгоритм с той же самой глобальной оценкой временной сложности, но со временем коррекции 0(\ogN), что сопоставимо с оценкой времени задержки поступления, установленной в теореме 3.10. Оба этих

Рис. 3.14. Опорные прямые из точки Pi к выпуклому многоугольнику С<_|.

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

Ключ к созданию эффективного открытого алгоритма дает следующее соображение: единственное, что необходимо, — это уметь быстро строить две опорные прямые к выпуклому многоугольнику, проходящие через некоторую точку (см. разд. 3.3.5). В частности, если точки обрабатываются в порядке р\, р2, ¦ . . и pi — текущая точка, то обозначим через C,-_i выпуклую оболочку множества {pi, р2, ¦ ¦ ¦, pi-\}- Необходимо построить из точки pi опорные прямые к C,_i, если они существуют (т. е. если точка pi является внешней для C,_i). Таких прямых не существует тогда и только тогда, когда точка pi является внутренней для С,_ь В последнем случае точка pi просто удаляется. В первом случае должна быть удалена соответствующая цепочка вершин, заключенная между двумя опорными точками, и вместо них должна быть вставлена точка pi. Эта ситуация показана на рис. 3.14. Для удобства мы будем называть опорную прямую левой или правой в соответствии с тем, по какую сторону она находится, если смотреть из точки р,- на С,_ь
Предыдущая << 1 .. 47 48 49 50 51 52 < 53 > 54 55 56 57 58 59 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed