Введение к работе
Актуальность темы. Известно, что одним из фундаментальных объектов математики является выпуклый многогранник. Это объясняется тем, что любое геометрическое тело, можно разбить на.компоненты, состоящие из выпуклых тел, которые в свою очередь, можно аппроксимировать' выпуклыми многогранниками. Учитывая, что многогранники описываются конечным числом данных, исследование и характеризация выпуклых тел посредством выпуклых многогранников остается и сейчас основным приемом. Этим и объясняется, что теория многогранников и связанные с ней геометрические методы имеют широкий выход в общую теорию поверхностей. Здесь следует также отметить, что выпуклые многогранники непосредственно появляются и при изучении.весьма далеких от них объектов. В качестве подтверждения этой мысли можно привести следующие примеры. Непустое множество решений конечной системы линейных нера--венств является выпуклым многогранником. Выпуклая оболочка конечного множества точек евклидова пространства есть также выпуклый многогранник. Другими словами, минимальным по объему выпуклым телом, содержащим п точек пространства, являетг . ся выпуклый многогранник. Конечную группу можно представить в виде группы симметрических преобразования выпуклого многогранника.
Уникальные творения природы, какими являются минералы Св частности, алмазы), имеют форму многогранников, либо близкую к ним.
Определенной простотой задания и построения выпуклых многогранников скорее всего объясняется то, что большинство изделия человеческоя деятельности имеют форму выпуклого многогранника или состоят из таких частей.
Таким образом, естественным является явное «ли неявное появление выпуклого многогранника во всех направлениях математики и ее приложениях.
Теория выпуклых многогранников состоит из двух основных направлений: комбинаторная теория, изучающая граф многогранника, и метрическая теория, изучающая метрические свойства выпуклого многогранника, т.е. рассматривающая выпуклый мно-
гограшшк как обьект евклидова метрического пространства.
Актуальним в последнее'время стало проведении специальных исследований на стыке . упомянутых направления, что позволяет создать более взаимосвязанную и цельную картину о многогранниках. Это направление исследований, которое названо автором комбинаторно-метрическим, посвящено распространению информации о комбинаторной структуре выпуклого многогранника при изучении его общих свойств, установлению взаимосвязей между комбинаторными и ' метрическими характеристиками многогранника, а также исследованию влияния изменений метрических характеристик многогранника на его комбинаторную структуру. Эти исследования, в большей степени, основаны на двухступенчатом способе задания многогранника, при котором многогранник определяется своим графом и необходимым списком метрических параметров. Настоящая диссертация посвящена комбинаторно-метрическим исследованиям выпуклого многогранника на базе применения единого подхода к изучению способов его задания, деформируемости, проектируемое выпуклого многогранника и приложению теоретических результатов к решению прикладных задач. Естественно, что каждое новое направление имеет предпосылки своего, возникновения и результаты, полученные в рамках известных раннее направлений математики. Краткий обзор результатов в \ теории многогранников, в частности, его комбинаторно-метрической части, изложен во введении диссертации. По комбинаторной теории приведены исследования Л.Эйлера о соотношении между числами вершин, ребер и граней выпуклого многогранника; теоремы Е.Штейница о количественной и качественной структуре графов выпуклых многогранников; В.Эберхарда и Б.Грюнбаума о последовательностях, являющихся степенями вершин или граней графов выпуклых многогранников; В-.Татта и др о числе комбинаторно различных выпуклых многогранников с В вершинами (Г гранями, Р рёбрами).' К комбинаторно-метрическим отнесены результаты О.Коши о единственности выпуклого иногог- . ранника, определяемого своими графом и гранями; А.Д.Милки и А.М.Гурина' об однозначной определенности выпуклого многогранника его графом я величинами ребер и двугранных углов (плоских углов); по задаче Е.Штейница о возможности реали-
_зяции 3-связного пллнарногп граіа в вило випуклого многогранника с наперед заданной гранью; П.Манн о возможности реализации таких графов с сохранением их груипн синнстрип; Б.Гршбаума к Мг.цкина о невозможности реализации каждого З-сі-'.'ігмого пленарного rpata в силе випуклого многогранника, вписываемого в ореру. По метрической теории отмечены исследования Г.Есйлл и Г.Мчнковского об изучении випуклого многогранника как множества решений і;о:шчноп системи линейных неравенств; Г.Миикоеского о существовании и единственности многогранника с наперед заданными вітаними нормалями и плесалн.чн граней; теореми А.Д.Алексаидрова о существовании и единственности выпуклого многогранника с данной разкерікой, с данники кривизнами верпиш и др.; В.Г.Бол-тннсксто, Солтана П.С. и Сслоусова ВЛ, об ссеїдаемести выпуклого многогранника; Хзмкера, Голубятников» Б.П. и других об опредсленнл випуклого тепа по рентгеновской проекции; Маргнни о восстановлении випуклого многогранника по его теневым проекциям.
Здесь следует отметить, что если современные исследования комбинаторной теории випуклого многогранника относится к дискретной математике (теория гримов, иечбинаюрика, теория групп, теория сложности), то метрическая зеория выпуклого многогранниі:а - это в большей степени раздел геометрии (теория випуклих тел). Комбинаторно-метрическая теория випуклого многогранника, осиовнваясь и развивая ядеи и кегодн дискретной математики, позволяет изучать общ'в структуру выпуклого многогранника. Тем самым, ксчбннатсрпо-.чеіричсскув теорию выпуклых многогранников в большей степени молшо отнести к дискретной математике Jt математическая кибернетике.
В настоящей диссертации изучаются вопросы комбинаторной и комбинаторно-метрической теории випуклих многогранников
в irs, имеющих естественнее теоретическое, либо' практическое значение. При этом больше значение отводится изучению различных, сложиостных характеристик выпуклого многогранника.
Исследование комбинаторной структуры выпуклого многогранника начинается с построения алгебры гра-рси многогранников на основе частичной операции -склепки'.' Здесь естественным является стремление з классе всех 3-связних планарных гра роз
выделить базис относительно этой операций -так, чтобы из элементов базиса можно было. с точностью до. изоморфизма синтезировать любой граф из этого класса. Представляет также интерес оценка сложности . синтеза произвольного графа З-кногогранника из базисных. Таким образом, мы приходим к специальному способу задания графов выпуклых многогранников. Такого рода исследования проводились'в метрической теории, где в качестве операции рассматривалась сумма . Минковского. Аналогичные исследования в теории натуральных чисел, как известно, привели к выделению простых чисел, с помощью, которых можно представить любое натуральное число.
Множество вершин графа выпуклого многогранника известным образом . определяет метрическое пространство относительно естественного расстояния кежду вершинами. Следовательно, с помощью понятия шара с ' центром в данной вершине можно изучать локальную окрестность вершины графа и по возможным расположениям различных шаров охарактеризовать структуру графа многогранника. В диссертации изучается задача упаковки шаров (коды на многогранниках). При этом задача рассматривается также и для случая, когда допускается пересечение шаров по сферам. Эти исследования тесно примыкают к задаче оценки 'комбинаторной изменчивости выпуклого-многогранника к различным деформациям, а также продиктованы стремлением распространить идеи теории кодов, исправляющих ошибки, на комбинаторную теорию многогранников.
Далее в диссертации описаны собственно комбинаторно-метрические исследования выпуклого многогранника.
Теоремы единственности дли выпуклых многогранников, т-е. теоремы об однозначной определенности выпуклого многогранника с теми или иными параметрами в некоторых случаях по-' рождают практические" (Эффективные) способы задания выпуклого многогранника.
В диссертации описывается, названный нами комбинаторно--метрическим^ способ однозначного с точностью до движения и отражения задания многогранника. Такое двухуровневое задание многогранника описывается совокупностью . двух типов параметров t комбинаторным, каким является граф многогранника (например, матрица инцидентности или смежности! и достаточным
. б
числом метрических параметров . (например, тройки координат 'вершин, четверки коэффициентов линейных неравенств, расстояния между вершинами). При этом оценивается сложность (минимальное число метрических параметров) комбинаторно-метрического способа задания для каждого из перечисленных типов метрических.параметров.
Такой двухуровневый подход диктует новее направление исследования, глубже раскрывавших, природу самих многогранников', и дает возможность сократить число метрических параметров, достаточных для- однозначного задания многогранника. Следует откетить, что способ задания многогранника при условии известности его графа имеет также и практический интерес. Например, при вводе в память ЭВМ большой серии многогранников заданого комбинаторного .типа.
Дальнейшие исследования касается вопросов, связанных с деформациями выпуклых многогранников. Предлагается подход к изучению, выпуклого многогранника в динамике, т.е. изучается влияние.непрерывных деформаций многогранника на изменение комбинаторной структуры.деформируемого многогранника. Описываются типы деформация, продиктованные различными способами задания, выпуклого многогранника. Деформациям многогранник подвергается посредством изменения положения вершин или граней. При этой в зависимости от' рассмотрения . вида системы координат (декартова или. сферическая); от того какие параметры подвергаются изменениям, в каких пределах изменяются выделенные параметры, порождаются различные типы деформаций. Устанавливаются взаимосвязи между различными типами деформаций.
Основные исследования направлены'на изучение классов
деформированных многогранников, порожденных от исходного
многогранника (порождающего многогранника). Актуальность
рассмотрения іслассов деформированных многогранников заклю
чается в том, что каждый многогранник из такого класса оп-
.ределяётся (в основном) поррйдающих хногогранником'и гекта
ром-изменений своих параметров.. Здесь 'возникает вопрос - о
перечислении.и подсчете комбинаторно различных многогранни
ков, порождаемых от исходного многогранника при тех или иных
типах деформаций. .
Число различных комбинаторных типов многогранников, Порождаемых от исходного многогранника в результате . применения данного типа деформаций рассматривается как мера комбинаторной изменчивости многогранника к этому типу . деформация. Классы деформированных многогранников возникают при моделировании естественного процесса роста, минералов;.' изготовлении изделия многогранной формы и т.д.
Далее описывается специальный способ проектирования 3-лерного выпуклого тела па 2-мерную поверхность Ссферу или плоскость) - f-проектирование. При этом- основная цель исследования состоит в решении обратной, задачи, т.е. в определении параметров многогранника по его р-проекции. Эти исследования, в свою очередь, порождают задачу изучения влияния изменения параметров многогранника на его р-проек-цкю, что привадит к рассмотрению классов деформируемых многогранников. Практическая же ценность этих исследований в том, что р-проекция моделирует лазерные рефдектограммы Сслецифическая картинка на экране, формируемая отражением и преломлением исходного плоско-параллельного лазерного потока от тела) прозрачных тел формы выпуклого многогранника. Эти исследования приводят к задачам специального освещения выпуклого, многогранника потоками параллельных лучея.' Научаются задачи определения минимального числа потоков, освещающих всю границу многогранника, устойчивого освєщєііия .многогранника,
Метод Р-проектирования распространен ; также на неоднородные выпуклые многогранники и ставится задача восстановления таких многогранников.
Р-проектирование и методы решения поставленных задач существенно отличаются от известных в литературе исследования по теневым, рентгеновским и другим типам проекция выпуклых ' тел.
И, наконец, в заключении приводятся приложения результатов диссертации к диагностике качества огранки бриллиантов, бесконтактному измерению геометрических параметров алмазов и методу оптимального раскроя алмазов.
''. Цшиж&Ші..исследование комбинаторной структуры выпук-гдого многогранника на базе синтеза графов многогранников от-
носительно их "склепки'' и упаковки шаров в графе-многогранни-.". ка. Описание и установление оценок сложности способов задания . выпуклого многогранника, базирующихся награде многогранника. Рассмотрения классов деформированных выпуклых многогранников. Сравнительный анализ таких классов при различных типах деформация и получение результатов об их комбинаторной, мощности (число комбинаторно неэквивалентных многогранников). Изучение специального способа проектирования ' (^.-проекции) выпуклого многогранника л- решение обратне-я задачи -. восстановление выпуклого многогранника по их ^-проекциям. Приложения теоретических результатов.'пря рсагения задач, автоматизация я оптимизации технологического процесса огранки алмазов.
10ИДа_всіущдо]ВанйЯх. 3 работе используются методы дкек-ретноя катекатнки и математической кибернетики.
Научная новизна, Все основные постановки задач и, основные результаты диссертации являются новыми. В диссертации установлены, достижимые нижние и верхние оценки сложности синтеза произвольного трехсвязного планерного графа, из базисных графов и разброса различных способов синтеза; описана последовательность графов многогранников с растущим числом вершин, имеющих совершенные d-коды.; получены окончательные результаты о сложности комбинаторно-метрического задания выпуклого многогранника при типах метрических параметров задания: вершинном, граневом и расстояниями; описаны' всё типы деформаций выпуклого многогранника, основанных на различных способах его задания, выделены комбинаторно устойчивые к деформациям выпуклые многогранники, оценено максимальное значение комбинаторной мощности класса деформированных многогранников при ограниченных деформациях выпуклого многогрішний с Г гранями; разработаны алгоритмический и аналитический йвтоды расчета ^-проекции выпуклого многогранника, сформулированы корректные постановки задачи определения выпуклого, многогранника по его p-проєкции, разработаны ссютветствуюяие методы решения обратной задачи; описаны приложения полученных теоретических.результатов в задачах"оценки.качества, огранки . бриллиантов,. бесконтактного' /.измерения . геометрических . параметров алмазов, оптикального раскроя алмазов.
ШМТИЧЄСаЖІЦЄОРетгаЄШ-ШШВІь. Диссертация в ос- ' новном носит теоретический характер. Подученные результаты . и разработанные, «етоди нашли свои "применения, отраженные б приложениях диссертации. Они также могут найти применение ь вычислительной геометрии, в теории оптимизации, в минералогии, в оптике.
Апробация работы, Результаты диссертации излагались ь
Международном математическом центре им." С.Банаха (Варшава,
1986),на Международном симпозиуме по теории информации (Моск
ва-Ташкент, 1384), на Советско-Итальянском симпозиуме по не
корректным и некраевым задачам математической физики (Самар
канд, 1991), на VII, уш,. IX '.Всесоюзних семинарах по теорети
ческой кибернетике (Иркутск, 1985.; Горький, 1308; Волгоград,
1990), на I и П Всесоюзных семинарах по дискретной 'математи
ке и ее приложениям (Москва, 1984, ISO?), на Всесоюзной школе -
по сложности управляющих систем (Новосибирск, 1989), на '. IX
Всесоюзной конференций по геометрии (Кишинев, .1508), Всесоюз
ном симпозиуме по вычислительной томографии (Ташкент, 1389),
на первом геммологическом совещании (Черноголовка, 1985), ' на
семинаре по кибернетике в МГУ. под руководством чл.-корр; РАН
С.В.Яблонского, на семинарах по дискретной математике, в НГУ,"
на семинарах по дискретной математике и ее". приложениям в .
ТашГУ. ;'...' '".'/''
ПуШщащик. Основные результати диссертации опубликованы
в 17 работах, список которых приводится в- конце'автореферата.
В совместных работах постановки задач, идеи решения'и основ
ные теоретические результаты, включенные в'диссертацию, при
надлежат диссертанту. Работы, освещающие приложения теорети
ческих результатов-, проведены совместно. ". "
Структура й обьем работы. Диссертация состоит из введения, пятиглав и списка "литературы. -Первая глава разбита на 2 параграфа, вторая - на г, третья - на 2, четвертая -. на 5, пятая - на 3. Обьем работы 2Ц страниц. Список литературы содержит 92 лаименованйя." -.