Вычислительная геометрия: Введение - Препарата Ф.
Вычислительная геометрия: Введение
Автор: Препарата Ф.Другие авторы: Шеймос М.
Издательство: М.: Мир, под редакцией Ю. М. Банковского
Год издания: 1989
Страницы: 478
ISBN 5-03-001041-6
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
Скачать:
Ф. Препарата, М. Шеймос
ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ : Введение
Перевод с английского
С. А. Вичеса, М. М. Комарова
под редакцией
Ю. М. Банковского
Москва «Мир» 1989
ББК 22.19 П72 УДК 681.3 513
Препарата Фм Шеймос М.
Вычислительная геометрия: Введение: Пер. с англ. — М.: Мир, 1989. —478 с.
ISBN 5-03-001041-6
Монография известных американских специалистов, содержащая основы разработки и анализа алгоритмов вычислительной геометрии. Изложение основано на детальном рассмотрении конкретных задач и алгоритмов их решения. Особое внимание уделено способам описания алгоритмов на упрощенном Алголе.
Для математиков-прикладников, аспирантов и студентов вузов как учебное пособие по машинному проектированию, машинной графике, распознаванию образов.
Редакция литературы по математическим наукам
) 1985 by Springer-Verlag New York Inc. All Rights Reserved. Authorized translation from English language edition published by Springer-Verlag Berlin Heidelberg New York Tokyo
Предисловие редактора перевода
В 1982 г. в издательстве «Мир» вышла книга А. Фокса и М. Пратта «Вычислительная геометрия. Применение в проектировании и прозводстве», в которой рассматриваются проблемы геометрического моделирования. И вот спустя 6 лет в книге по существу с таким же названием речь идет совсем о другом, а именно об оценке сложности геометрических вычислений, об анализе и построении эффективных комбинаторных алгоритмов для решения геометрических задач. Парадокс объясняется просто: как одно, так и другое научное направление родилось совсем недавно, около 15 лет назад, их становление и интенсивное развитие протекали одновременно, оба направления имеют глубокие геометрические корни и самым непосредственным образом связаны с применением ЭВМ. К настоящему моменту предмет исследований в каждом из направлений обрел четкие очертания и в специальной литературе за одним из них утвердилось название — «Геометрическое моделирование», а за другим, которому и посвящена данная книга, — «Вычислительная геометрия».
Книга Ф. Препараты и М. Шеймоса — первая в мировой литературе монография, в которой систематизированы результаты, рассеянные по многочисленным журнальным статьям и отчетам. Эту книгу долго ждали, ссылки на нее появились значительно раньше, чем она вышла в свет.
Вычислительная геометрия имеет широкий круг применений. Это робототехника, распознавание образов, проектирование СБИС, базы данных, машинная графика, раскрой материалов и т. д. Популярность вычислительной геометрии непосредственно связана с визуализацией вычислений и, как следствие, с удобством геометрической интерпретации необязательно геометрических объектов.
Читатель увидит, что вычислительная геометрия опирается на многие разделы как классической, так и современной мате-
6 Предисловие редактора перевода
матики. Богатство математического аппарата и широта применения вычислительной геометрии серьезно осложнили работу над переводом. Определенные трудности создавала также принятая в американской литературе образность терминов, противоречащая сложившейся традиции в русской научно-технической литературе.
При переводе были исправлены мелкие ошибки (но нет гарантии, что не допущены другие). Часть таких ошибок любезно указал Ф. Препарата. Он же внес отдельные изменения в текст книги, сделав ее более современной. Мы благодарны проф. Ф. Препарате за внимание, с которым он отнесся к русскому изданию.
Большую помощь при переводе и редактировании книги оказали большие энтузиасты вычислительной геометрии Н. М. Корнеенко и Б. М. Чудинович. Их советы и замечания безусловно содействовали улучшению качества книги. К сожалению, в нашей стране людей, активно работающих в новой, актуальной области весьма и весьма мало. Поэтому можно присоединиться к Ф. Препарате, выразившему надежду, что появление книги на русском языке привлечет внимание молодых математиков и информатиков к новой и быстро развивающейся области научного поиска и соревнования.
Перевод книги выполнен С. А. Внчесом (гл. 1, 2, 7, 8) и М. М. Комаровым (гл. 3, 4, 5, 6).
Апрель 1988
Ю. Банковский
Предисловие автора к русскому изданию
Прошло 3 года с момента выхода книги на английском языке, и теперь я с удовольствием приветствую ее перевод на русский язык. В течение этого короткого периода времени стремительные темпы развития вычислительной геометрии возросли еще больше. Ряд задач, которые оставались нерешенными почти десятилетие, были либо полностью решены, либо на пути к их решению были получены блестящие результаты. Поэтому я с радостью воспользовался предоставленной мне возможностью внести изменения в те предложения и абзацы книги, которые в связи с самыми последними достижениями несколько устарели. Сегодня исследования в вычислительной геометрии продолжаются так же энергично, как и прежде. Я надеюсь, что эта книга сможет способствовать увеличению числа наших коллег в Советском Союзе, присоединившихся к этому благородному и увлекательному состязанию.
Февраль 1988 г.
