Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
— выпуклый (convex) 32
--обобщенный (generalizide convex) 387
— грани (facets) 32
— простой (simple) 32
— ребра (edges) 72 Полюс (pole) 40 Поляра (polar) 40
Поляритет (polarity) 40, 355, 374
Порядок дерева (order) 46
Построение Евклидово (Euclidian construction) 10
Преобразование двойственности (duality transformation) 39
— линейное (linear mappings) 34 Преобразуемость (transformability)
44
(N) -преобразуемость ((N) -transformability) 44
Приведение к абсурду (reductio ad absurdum) 10
Присваивание (assignment) 18
Промежутки (gaps) 313, 418
Простота (simplicity) 12
Противолежащие пары (antipodal) 219
Процедура (procedure) 17 Прямая (line) 30
— опорная (supporting) 142, 143, 146 Прямолинейный объект (flat) 115 Прямолинейный отрезок см. Отрезок
прямолинейный Прямоугольник активный (active rectangle) 426, 437
— обобщенный (generalized) 94, 98 Псевдоалгол (Pidgin Algol) 17 Псевдовершины (pseudovertices) 379
Разбиение планарное 63 Развилка (fork) 26, 421 Разделимость линейная (linearly separated) 260, 262 Расписание (schedule) 398, 399
— гомотопное (homotopic) 399
— последовательное (serial) 399
— частичное (partial) 399 Расслоение (layering) 108 Расстояние (distance) 36
— вертикальное (vertical distance)
378
— хаусдорфово (Hausdorff) 277 Расцепление 158, 159
Реберный список с двойными связями
(double-connected-edge-list) 27,
74, 174 Ребро (edge) 31, 32, 117 Регуляризация (regularitation) 71,72 Режим отчета (report mode query)
91—93, 110 — подсчета (count-mode query) 91,
93
Робастность (robustness) 210 №-распределения (Np-distributions) 185
Сведение (reduction) 87, 194
— транзитивное (transitive) 87 Связанные точки (connected points)
424
Сдвиг циклический (rotate) 99 Симплекс-метод (simplex algorithm) 354
d-симплекс (d-simplex) 118 Скелет (skeleton) 320 Словарь (dictionary) 345 Сложность алгоритма (algorithm complexity) 173
— в среднем случае (average case)
20
--худшем случае (worst-case) 20,
186
— временная (time) 20
— пространственная (space) 20 Сопряжение (conjugate) 424 СВ-сопряжение (NE-conjugate) 424 ЮЗ-сопряжение (SW-conjugate) 424 Сортировка (sorting) 120, 133
— топологическая (topological sor-
ting technique) 88 Список (list) 23, 108
— реберный 119
— смежности 119
— точек событий (event-point sche-
dule) 21, 64, 344, 409 Срединные оси (medial axis) 320 Статус заметающей прямой (sweep-line status) 21, 65, 71, 84, 344, 403, 409, 437 Стек (stack) 23
Степень доминирования (dominance depth) 225
— узла (node count) 404 Структура данных (data structure)
22
--динамическая (dynamic) 90, 93
--статическая (static) 24, 90
— первичная (primary) 438 Сцепление 158, 159
476
Предметный указатель
Точка (point) 30
— крайняя (extreme) 120, 125, 145 Точки аффинно независимые (affinely independent points) 115
— Штейнера (Steiner points) 323 Транзакция (transaction) 397, 399,
400
Трапеция (trapezoid) 80 Триангуляция (triangulation) 32, 74, 76, 175, 270, 285
— Делоне 273, 280, 286
— жадная (greedy) 286, 287, 290
— Киркпатрика 75
— конечного множества точек (of а
finite set) 32
— монотонного многоугольника 292 Тупик (deadlock) 399
Угол выпуклый (convex angle) 162 Узел непродуктивный (unproductive node) 98
— продуктивный (productive) 98
— реберный (edge) 28
Узлы отнесения (allocation nodes)
26, 105, 421 Указатель Уилларда—Люкера НО Условие (condition) 18
Функция (function) 18
— взятия целой части (flor function)
189
— регрессии (regression function)
214, 215
--монотонная (isotonic) 215, 216
— унимодальная (unimodal function)
Хвост списка (list-tail) 366
Центральное проецирование (central
projection) 37, 40 Центроид 59, 128 Цепь (circuit) 66, 72, 431
— внешняя (external) 431
— внутренняя (internal) 431
— монотонная (monotone) 67, 68
— нетривиальная (nontrivial) 431
— ориентированная (directed) 431 —• тривиальная (trivial) 431 Цикл (loop) 18
Шаг^продвижения (advancing step)
— слияния (merge step) 198
Эйлера теорема 65, 78
— формула 32, 75, 79, 119, 160, 258 Экватор (equator) 385 Эквивалентность (equivalent) 44 Элементарная операция (primitive
operation) 41 Этап (stage) 278
Ядро (kernel) 31, 61, 392
— плоского многоугольника 364 Ячейки Дирихле (Dirichlet cell complexes) 324
Оглавление
Предисловие редактора перевода .... Предисловие автора к русскому изданию . Предисловие............
1.
Введение
1.1. Исторический обзор................... 10
1.2. Алгоритмические основы................. 16
1.3. Геометрические предпосылки................ 29
1.4. Модели вычислений................... 41
2.
Геометриче
2.1. Введение в геометрический г
2.2. Задачи локализации точки .
2.3. Задачи регионального поиск
2.4. Замечания и комментарии
2.5. Упражнения......
