|
Оглавление
Предисловие редактора перевода................5 Предисловие автора к русскому изданию............7 Предисловие........................8 Глава 1. Введение.................. 10 1.1. Исторический обзор................... 10 1.2. Алгоритмические основы................. 16 1.3. Геометрические предпосылки................ 29 1.4. Модели вычислений................... 41 Глава А. Геометрический поиск..............52 2.1. Введение в геометрический поиск..............52 2.2. Задачи локализации точки.................57 2.3. Задачи регионального поиска...............88 2.4. Замечания и комментарии................11О 2.5. Упражнения......................113 Глава О. Выпуклые оболочки: основные алгоритмы...... 114 3.1. Предварительные сведения................ 115 3.2. Постановка задачи и нижние оценки сложности........ 120 3.3. Алгоритм построения выпуклой оболочки на плоскости...... 125 3.4. Выпуклые оболочки в пространствах размерности большей двух.. 159 3.5. Замечания и комментарии................ 178 3.6. Упражнения...................... 181 Глава т. Выпуклые оболочки: расширения и приложения... 183 4.1. Расширения и варианты.................183 4.2. Приложения в статистике................. 210 4.3. Замечания и комментарии.................223 4.4. Упражнения..................,... 225 Глава О. Близость: основные алгоритмы..........226
5.1. Набор задач......................227
5.2. Задача о единственности элементов.............233
5.3. Нижние оценки.....................235
5.4. Решение задачи о ближайшей паре методом «разделяй и властвуй» 238
5.5. Решение задач о близости методом локусов; диаграмма Вороного 249
5.6. Решение задач о близости с помощью диаграммы Вороного.... 269
5.7. Замечания и комментарии.................272
5.8. Упражнения......................274
Глава О. Близость: варианты и обобщения.........276
6.1. Евклидовы минимальные остовные деревья.......... 276
6.2. Пленарные триангуляции................. 285
6.3. Обобщения диаграммы Вороного.............. 295
6.4. Промежутки и покрытия................. 313
6.5. Замечания и комментарии................. 320
6.6. Упражнения...................... 323
Глава /. Пересечения................. 326
7.1. Примеры из приложений................. 327
7.2. Плоские приложения................... 332
7.3. Трехмерные приложения................. 373
7.4. Замечания и комментарии................. 389
7.5. Упражнения...................... 393
Глава б. Геометрия прямоугольников...........394
8.1. Некоторые приложения геометрии прямоугольников......394
8.2. Область применения результатов..............400
8.3. Общие замечания по алгоритмам статического типа......402
8.4. Мера и периметр объединения прямоугольников........404
8.5. Контур объединения прямоугольников............414
8.6. Замыкание объединения прямоугольников..........424
8.7. Внешний контур объединения прямоугольников........430
8.8. Пересечения прямоугольников и связанные с этим задачи.... 436
8.9. Замечания и комментарии................452
8.10. Упражнения......................453
Литература........................455
Именной указатель....................469
Предметный указатель................... 471
|