Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 24»

SI /" t Кибернетический сборник НОВАЯ СЕРИЯ :;"' ; ВЫПУСК 24 Сборник статей Перевод с английского ПОД РЕДАКЦИЕЙ О. Б. ЛУПАНОВА '*'«' МОСКВА «МИР» 1987 ББК 32. 81 К 38 УДК 519. 95 К38 Кибернетический сборник. Новая серия Вып. 24 Сб. ста- статей: Пер. с англ. —М. : Мир, 1987. — 232 с, ил. Продолжение серии, начатой изда1ельством «Мир» в 1965 г. В данном вы- выпуске большой интерес представляет обзор Д. Ли и Ф. Препараты (США) основ- основных результатов по вычислительной геометрии. Специалистов по комбинаторике, теории кодирования, дискретного анализа, алгебры и др. заинтересует цикл ста- . тей но сильно регулярным графам и частичным геометриям, написанных К. Юбо (Бельгия), А. Браувером и И. ван Линтом (США). Включены также небольшие статьи Л. Вэльяита, X. Коэна и X. Леистры (США) по теории сложности и теории графов. Для научных работников, инженеров-исследователей, аспирантов и студентов, занимающихся и интересующихся теоретической кибернетикой и ее приложениями. К 170042;™°!-7463 4-87, ч. 1 ББК 32. 8. •л ;t Редакция литературы по математическим наукам t ■ ; , . , . J iL-'... © состав, перевод на русский язык, «Мир», 1987 Вычислительная геометрия. Обзор ') ■ Д. Лиг), Ф. Препарате*), Дается обзор исследований в области вычислительной геометрии — дис- дисциплины, предметом исследований которой является сложность решения гео- геометрических задач в рамках теории анализа алгоритмов. Эта недавно воз- возникшая область исследований уже нашла многочисленные приложения в различных других областях, таких, как машинное проектирование, машинная графика, исследование операций, распознавание образов, робототехника и ста- статистика. Обсуждаются пять главных направлений исследований: выпуклые оболочки, пересечения, поиск, близость и комбинаторная оптимизация. На при- примерах демонстрируются семь методов разработки алгоритмов: итерационное конструирование, заметание плоскости, геометрическое место точек, «разделяй и властвуй», геометрическое преобразование, поиск с отсечением и динами- динамизация. Также включен набор преобразований задач, позволяющих получать нижние оценки сложности решения геометрических задач в рамках модели построения/проверки. Ключевые слова и фразы. Алгебраическое дерево вычислений, анализ ал- алгоритмов, комбинаторная оптимизация, вычислительная сложность, вычисли- вычислительная геометрия, выпуклая оболочка, метод «разделяй и властвуй», метод динамизации, метод геометрического преобразования, метод заметания плос- плоскости, близость. I. ВВЕДЕНИЕ < ■ ' . Вычислительная геометрия, как она представляется сегодня занимается исследованием вычислительной сложности решения геометрических задач в рамках теории анализа алгоритмов. Однако словосочетание «вычислительная геометрия» использо- использовалось, по крайней мере дважды, в смысле, отличном от ука- указанного выше. В работах [47, 146, 299] изучались вопросы мо- ') Lee D. Т. , Preparata Franco P. Computational geometry — A survey. — IEEE Transactions on Computers, 1984, v. C-33, No. 12, p. 1072—1101. 2) Senior member, IEEE, Department of Electrical Engineering and Com- Computer Science, Northwestern University, Evanston. 3) Fellow, IEEE, Coordinated Science Laboratory, University of Illinois, Urbana, ■ЙНГИ-*??*'1.