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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 180 >> Следующая


3.6. Упражнения

1. Простая замкнутая ломаная. На плоскости заданы N точек. Построить простой многоугольник, вершинами которого являются данные точки.

(a) Показать, что нижняя оценка сложности алгоритма, решающего эту задачу, равна Q(iVlogA^).

(b) Разработать алгоритм решения этой задачи. (Указание: модифицировать метод обхода Грэхема.)

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

(a) Сколько общих опорных прямых могут иметь Р, и Р2?

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

3. Разработать алгоритм, выполняющий за постоянное время классификацию вершины v (как вогнутой, опорной или выпуклой) выпуклого многоугольника относительно отрезка pv, где р — заданная точка на плоскости.

4. Для алгоритма реального времени построения выпуклой оболочки на плоскости из разд. 3.3.6:

(a) доказать, что в случаях 2, 4, 6 и 8, показанных на рис. 3.16, точка /; с необходимостью является внешней для многоугольника Р;

(b) предположив, что р является внутренней точкой многоугольника Р, подумать, как процедура поиска обнаружит эту ситуацию.

5. Для метода поддержки динамической выпуклой оболочки из разд. 3.3.7:

(a) написать программу на псевдоалголе, реализующую функцию СОЕДИНИТЬ(U\, U2), вычисляющую опорный отрезок для В-оболочек Ui и Uf,

(b) разработать спаренные процедуры ПОДЪЕМ-СПУСК для выполнения операции удаления точки из множества на плоскости.

6. Кейл — Киркпатрик. П>сть 5 — множество из N точек на плоскости с целочисленными координатами в интервале от 1 до Nd, где d — константа. Показать, что выпуклую оболочку множества S можно найти за линейное

7. Зейдель. Пусть S = {рь .... pv] с: Е* и х(р,)< х(р2)< ... < *(р«). Показать, что, несмотря на априорное знание порядка следования точек множества 5 на оси х, нижняя оценка сложности построения выпуклой оболочки множества S по-прежнему остается равной Q(N log N). (Указание:

182

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

использовать преобразование, переводящее задачу о выпуклой оболочке на плоскости в данную.)

8. Зейдель. В алгоритме «заворачивания подарка» Чанда — Капура необходимо поддерживать структуру данных для множества Q из (d — 2) гиперграней, которые могут быть «завернуты» на последующих шагах обработки. В этом алгоритме можно печатать гиперграни сразу же после того, как они найдены и нет необходимости запоминать их. Таким образом, размер структуры данных для Q определяет емкостную сложность алгоритма «заворачивания подарка». Пусть 5 — множество из п точек в пространстве Ed, находящихся в общем положении.

(a) Показать, что если для построения выпуклой оболочки множества S используется алгоритм «заворачивания подарка», то существует некоторая последовательность шагов «заворачивания подарка», такая, что размер Q никогда не превышает максимального числа гиперграней политопа с N вер-

(b) Разработать вариант алгоритма «заворачивания подарка» с емкостной сложностью

0(<Pd-2) = 0(°L(d"1)/2J).

где ф<*_1 — число гиперграней политопа.

9. Показать, что в алгоритме построения с(-мерной выпуклой оболочки методом «под-над» (разд. 3.4.2) классификация каждой из N вершин политопа Р как вогнутой, выпуклой или опорной может быть выполнена за время 0(<P<*-i) + 0(Nd), где фй-! —число гиперграней политопа Р.

ГЛАВА

Выпуклые оболочки: расширения и приложения

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

4.1. Расширения и варианты 4.1.1. Анализ среднего случая

Возвращаясь к обсуждавшимся в разд. 3.3 алгоритмам построения выпуклой оболочки на плоскости, следует отметить, что независимо от исходных данных алгоритм Грэхема всегда требует О (N log N) времени, так как в начале он выполняет сортировку данных. Напротив, время работы алгоритма Джарвиса колеблется от линейного до квадратичного, и в связи с этим уместно поставить вопрос: каково среднее время работы алгоритма? Поиск ответа на этот вопрос приведет в сложную и вместе с тем «захватывающую» область стохастической геометриии, где мы познакомимся с некоторыми трудностями, касающимися анализа поведения геометрических алгоритмов в среднем случае.

Так как алгоритм Джарвиса имеет сложность O(hN), где h — число вершин выпуклой оболочки, то для оценки сложности этого алгоритма в среднем необходимо лишь вычислить E(h) —математическое ожидание величины п. Для этого надо
Предыдущая << 1 .. 61 62 63 64 65 66 < 67 > 68 69 70 71 72 73 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed