Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
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) —математическое ожидание величины п. Для этого надо