Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
3.1
, Выпуклые оболочки: основные алгоритмы...... 114
3.1. Предварительные сведения................ 115
3.2. Постановка задачи и нижние оценки сложности........ 120
3.3. Алгоритм построения выпуклой оболочки на плоскости...... 125
3.4. Выпуклые оболочки в пространствах размерности большей двух . . 159
3.5. Замечания и комментарии................ 178
3.6. Упражнения...................... 181
ва 4.
Выпуклые оболочки: расширения и приложения .
4.1. Расширения i
4.2. Приложения i
4.3. Замечания и комментарии.................223
4.4. Упражнения......................225
478
Оглавление
5.
Близость: основные алгоритмы .
5.1. Набор задач......................227
5.2. Задача о единственности элементов.............233
5.3. Нижние оценки.....................235
5.4. Решение задачи о ближайшей паре методом «разделяй и властвуй» 238 '.5; Решение задач о близости методом - локусов; диаграмма Вороного 249
!б. Решение задач о близости с помощью диаграммы Вороного .... 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
Глава 7. Пересечения.................326
7.1. Примеры из приложений.................327
7.2. Плоские приложения...................332
7.3. Трехмерные приложения.................373
7.4. Замечания и комментарии.................389
7.5. Упражнения......................393
Глава 8. Геометрия прямоугольников...........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
УВАЖАЕМЫЙ ЧИТАТЕЛЬ!
Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва, И—ПО, ГСП, 1-й Рижский пер., д. 2, издательство «Мир».
Научное издание
Франко Препарата Майкл Шеймос
ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ: ВВЕДЕНИЕ
Зав. редакцией чл.-корр. АЩСССР В/ И. Арнольд Зам. зав. редакцией А. С. Попов Научи, редактор. М. В. Хатунцева Мл. научн. редактор Л. А. Королева Художник Г. М. Чеховский Художественный редактор В. И. Шаповалов Технический редактор 3. И. Резник Корректор М. А. Смирнов
И Б № 6477
Сдано в набор 17.05.88. Подписано к печати 27.12.88. Формат 60X90'/и- Бумага кн.-журн. Гарнитура латинская. Печать высокая. Объем 15 бум. л. Усл. печ. л. 30. Усл. кр.-отт. 30. Уч.-изд. л.
471. Цена 2 р. 80 к. Издательство «Мир» Москва, 1-й Рижский пер., 2.
Отпечатано с набора Ленинградской типографии № 2 головного предприятия ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграфпрома при Государственном ко-
фии и книжной торговли. 198052, г. Ленинград, Л-52, Измайловский пр., 29 в Ленинградской типографии № 4 ордена Трудового Красного Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзполиграф-