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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 180 >> Следующая


Необходимо упомянуть о методе Ван Леювена и Вуда [van Leeuwen, Wood (1980)], общей идеей которого является организация файла как набора отдельных структур данных, для того чтобы любая корректировка строго ограничивалась одной (или, возможно, небольшим фиксированным числом) из них; однако.

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

113

чтобы избежать переноса центра тяжести с корректировок на поисковую работу, необходимо не допускать чрезмерной фрагментации, поскольку запросы обычно относятся ко всей совокупности данных. Самое современное и всестороннее исследование состояния дел в области «динамизации» — это диссертация Овермарса [Overmars (1983)], и мы настоятельно рекомендуем обратиться к ней.

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

1. Провести более глубокий анализ метода детализации триангуляции Киркпатрика и выбрать К таким, чтобы достигнуть значения а 59/63. (Указание: оценить отдельно узлы со степенью больше К и узлы со степенью не больше Л'.)

2. Зейдель. Пусть S — множество из N точек на плоскости и А — пленарное подразбиение с Q(N) областями.

(а) Показать, что необходимо Q(N log iV) времени для локализации всех точек из S в А.

(б) Предположим теперь, что известна триангуляция 5. Триангуляция содержит информацию о том, как точки нз 5 расположены относительно друг друга. Эта информация могла бы помочь при локализации всех точек из S в А. Показать, что, несмотря на знание триангуляции 5, все же понадобится Q(NlogN) времени для локализации всех точек из S в А.

3. Доказать теорему 2.10. Предположить, что поиск состоит из / этапов с возрастанием мелкости сеток, и получить (Nc\ с, log ЛО-алгоритм с минимальным значением с2. Выразить с, и с2 как функции от I.

4. Можно ли модифицировать дерево регионов в варианте Уилларда — Люкера так, чтобы получить (N logd—1 N, log"-1 Л?)-алгоритм для задачи регионального поиска типа подсчета при d ^ 2? Строго обосновать свой ответ.

5. Эдельсбруннер — Гибас — Столфи. Рассмотреть метод цепей для задачи плоской локализации точки на Л^-вершинной карте и модифицировать его следующим образом. Начать с назначения этих цепей узлам дерева Т первичной структуры, как это показано в работе [Lee, Preparata (1978)] (см. разд. 2.2.2.2), так что каждому узлу v из Т назначена последовательность Y(v), состоящая из концов ребер его цепи; затем для каждого нелистового узла v сформировать У*(и), дополняя Y(v) всеми членами последовательности ОБЪЕДИНЕНИЕ(У*(ЛСЫН[и]),У*(ПСЫН[1>])). Каждый список Y*(v) представляет разбиение вертикальной прямой: создать указатель от каждого отрезка из Y*(v) к каждому из отрезков в У*(ЛСЫН[о]) или в У*(ПСЫН[и]), с которым он пересекается. Это определяет структуру данных для поиска Т*.

(а) Показать, что для запоминания Т* можно затратить O(N) памяти.

(б) Показать, что локализация точки па плоскости требует O(IogJV) времени.

6. Применить метод локализации при решении следующей задачи (круговой региональный поиск с фиксированным радиусом): даны N точек на плоскости и число d > 0, требуется перечислить точки, находящиеся на расстоянии, не превышающем d от заданной пробной точки q (возможно, затратив при этом дополнительно логарифмическое время).

ГЛАВА

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

Задача вычисления (построения) выпуклой оболочки не только является центральной в целом ряде приложений, но и позволяет разрешить ряд вопросов вычислительной геометрии, на первый взгляд не связанных с ней. Построение выпуклой оболочки конечного множества точек, и особенно в случае точек на плоскости, уже довольно широко и глубоко исследовано и имеет приложения, например, в распознавании образов [Akl, Toussaint (1978); Duda, Hart (1973)], обработке изображений [Rosenfeld (1969)], а также в задаче раскроя и компоновки материала {Freeman (1974); Sklansky (1972); Freeman-Shapira (1975)].

Понятие выпуклой оболочки множества точек S является естественным и простым. В соответствии с определением — это наименьшее выпуклое множество, содержащее 5. Чтобы наглядно представить это понятие в случае, когда 5 — конечное множество точек на плоскости, предположим, что это множество охвачено большой растянутой резиновой лентой. Когда лента освобождается, то она принимает форму выпуклой оболочки.

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

Предметом этой главы является построение выпуклой оболочки на плоскости и в пространствах более высокой размерности. В следующей главе будут рассмотрены приложения, различные варианты задачи о выпуклой оболочке и некоторые связанные с ней, но отличные по существу задачи. Чтобы избежать повторений, удобно ввести подходящую совокупность понятий,

3.1. Предварительные сведения

115

относящихся к выпуклой оболочке в пространстве произвольной размерности (Grunbaum (1967); Rockafellar (1970); McMullen, Shephard (1971); Wee (1966)]. В случае плоскости и трехмерного пространства эти понятия приобретают очень простой смысл. Этому посвящен следующий раздел. В дальнейшем мы часто будем ссылаться на понятия, введенные в разд. 1.3.1.
Предыдущая << 1 .. 34 35 36 37 38 39 < 40 > 41 42 43 44 45 46 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed