Комбинаторно-метрический подход к исследованию способов задания, деформируемости и Р-проектируемости выпуклого многогранника в R3 тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГ6 од

1 о шя

£с1.:сси ЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи

ПУЛАТОВ Абдимажид Каюмович

УДК 519.95

КОМБИНАТОРНО-МЕТРИЧЕСКИЙ ПОДХОД К ИССЛЕДОВАНИЮ СПОСОБОВ ЗАДАНИЯ, ДЕФОРМИРУЕМОСТИ И Р-ПРОЕКТИРУЕМОСТИ ВЫПУКЛОГО МНОГОГРАННИКА В Я3

Специальность 01.01.09 — Математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск — 1993

Работа выполнена на кафедре прикладной математики факультета прикладной математики и механики Ташкентского государственного университета.

Официальные оппоненты: доктор физико-математических

наук, В. П. Голубятников;

доктор физико-математических наук, п рофессор В. А. Емеличев;

доктор физико-математических наук, А. Д. Коршунов.

Ведущая организация — Вычислительный центр РАН.

Защита диссертации состоится « ¿^ь 1993 г.

в ^ , час. мин. на заседании специализированного

Совета Д 002.23.03 при Институте математики СО РАН (630090, Новосибирск, 90, Университетский проспект, 4).

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан « » 1 одз г

Ученый секретарь специализированного Совета Д 002.23.03,

доктор физико-математических наук А. В. КОСТОЧКА

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теми. Известно, что одни и из фундаментальных объектов математики является выпуклый многогранник. Это объясняется тем, что любое геометрическое тело, можно разбить на.компоненты, состоящие из выпуклых тел, которые в свою очередь, можно аппроксимировать' выпуклыми многогранниками. Учитывая, что многогранники описываются конечным числом данных, исследование и характеризация выпуклых тел посредством выпуклых многогранников остается и сейчас основным приемом. Этим и объясняется, что теория многогранников и связанные с ней геометрические методы имеют широкий выход в общую теорию поверхностей. Здесь следует также отметить, что выпуклые многогранники непосредственно появляются и при изучении .весьма далеких от них объектов. В качестве подтверждения этой мысли можно привести следующие примеры. Непустое множество решений конечной системы линейных нера--венств является выпуклым многогранником. Выпуклая оболочка конечного множества точек евклидова пространства есть также выпуклый многогранник. Другими словами, минимальным по объему выпуклым телом, содержащим п точек пространства, являет. ся выпуклый многогранник. Конечную группу можно представить в виде группы симметрических преобразований выпуклого многогранника. .

Уникальные творения природы, какими являются минералы Св частности, алмазы), имеют форму многогранников, либо близкую к ним.

Определенней простотой задания и построения выпуклых многогранников скорее всего объясняется то, что большинство изделия человеческой деятельности имеют форму выпуклого многогранника или состоят из таких частей.

Таким образом, естественным является явное «ли неявное появление выпуклого многогранника во всех направлениях математики и ее приложениях.

Теория выпуклых многогранников состоит из двух основных направлений: комбинаторная теория, изучающая граф многогранника, и метрическая теория, изучающая метрические свойства выпуклого многогранника, т.е. рассматривающая выпуклый мно-

■з

гогранник как объект евклидова метрического пространства.

Актуальным в последнее'время стало проведении специальных исследований на стыке . упомянутых направления, что позволяет создать более взаимосвязанную и цельную картину о многогранниках. Это направление исследований, которое названо автором комбинаторно-метрическим, посвящено распространений информации о комбинаторной структуре выпуклого многогранника при изучении его общих свойств, установлению взаимосвязей между комбинаторным!! и ' метрическими характеристиками многогранника, а также исследованию влияния изменений метрических характеристик многогранника на его комбинаторную структуру. Эти исследования, в большей степени, основаны на двухступенчатом способе задания многогранника, при котором многогранник определяется своим графом и необходимым списком метрических параметров. Настоящая диссертация посвящена комбинаторно-метрическим исследованиям выпуклого многогранника на базе применения единого подхода к изучению способов его задания, деформируемости, проектируемое™ выпуклого многогранника и приложению теоретических результатов к решению прикладных задач. Естественно, что каждое новое направление имеет предпосылки своего. возникновения и результаты, полученные в рамках известных раннее направлений математики. Краткий обзор результатов в \ теории многогранников, в частности, его комбинаторно-метрической части, изложен во введении диссертации. По комбинаторной теории приведены исследования Л.Эйлера о соотношении между числами вершин, ребер и граней выпуклого многогранника; теоремы Е.Штейница о количественной и качественной структуре графов выпуклых многогранников; В.Зберхарда и Б.Грюнбаума о последовательностях, являющихся степенями вершин или граней графов выпуклых многогранников; В-.Татта и др о числе комбинаторно различных выпуклых многогранников с В вершинами (Г гранями, Р рёбрами).' К комбинаторно-метрическим отнесены результаты О.Коши о единственности выпуклого многог- . ранника, определяемого своими графом и гранями; А.Д.Милки и А.М.Гурина об однозначной определенности выпуклого многогранника его графом и величинами ребер и двугранных углов (плоских углов); по задаче Е.Штейница о возможности реали-

зашш 3-свпзчогп нланаркогп rpa-ia в вило выпуклого многогранника с наперед заданной гранью: П.Мали о возможности реализации таких графов с сохранением их группа симметрии; Б.ГрюнСаума к Мсцкика о невозможности реализации каждого З-св.чгного нланарнпго графа в силе выпуклого многогранника, вписываемого в сферу. По метрической теории отмечены исследования Г.Бсйлл и Г.Мкнковского об изучении выпуклого многогранника как мнг'жссгиа решения конечной системы линейных неравенств; Г.Минкое-.-кого о супсствовоиии и единственности яняуклого мнсгсграчника с напорол зплашшии виеашш нормалями и плеса лини граней; теоремы А.Д.Александрова о существования и слшгстсшшостл выпуклого многогранника с дайной развер1Хой, с данными кривизнами Еегзин и др.; В.Г.Бол-тинскего, Солтана П.С. и Еелоусова О.Ф. об ссоааемссти выпуклого многогранника; Хаккора, Гояубятиикгка В.П. и других об определении выпуклого тела по рентгеновской проекции; Мартини о восстановлении выпуклого многогранника по его теневым проекциям.

Здесь следует отметить, что если современные исследования комбинаторной теории выпуклого многогранника относятся к дискретной математике (теория грифов, иснЗинащжка, теория групп, теория сложности), то метрическая теория выпуклого многогранника - это в большей степени раздел геометрии (теория выпуклых тел). Комбинаторно-метрическая теория выпуклого многогранника, основываясь и развивая идеи и методы дискретной математики, позволяет изучать общи структуру выпуклого многогранника. Тем самый, кснбинатсрпо-.четричсскуп теорию выпуклых многогранников в большей степени молшо отнести к дискретноя математике и математической кибернетике.

В настоящей диссертаций изучаются вопросы комбинаторной и комбинаторно-метрической теории выпуклых многогранников

в irs, имеющих естественнее теоретическое, лкСо' практическое значение. При этом больпюс значение отводится изучении различных. сяожиостных характеристик выпуклого многогранника.

Исследование комбинаторной структуры выпуклого многогранника начинается с построения алгебры rpa-fen кногогракннкав на основе частичной операции -склелкк'.' Здесь естественный является стремление в классе всех з-свягных планарных градов

выделить базис относительно этой операций -так, чтобы из элементов базиса можно было. с точностью до. изоморфизма синтезировать любой граф из этого класса. Представляет также интерес оценка сложности .синтеза произвольного графа 3-многогранника из базисных. Таким образом, мы приходим к специальному способу задания графов выпуклых многогранников. Такого рода исследования проводились'в метрической теории, где в качестве операции рассматривалась сумма . Минковского. Аналогичные исследования в теории натуральных чисел, как известно, привели к выделению простых чисел, с помощью, которых можно представить любое натуральное число.

Множество вершин графа выпуклого многогранника известным образом . определяет метрическое пространство относительно естественного расстояния между вершинами. Следовательно, с помощью понятия шара с ' центром в данной вершине можно изучать локальную окрестность вершины графа и по возможным расположениям различных шаров охарактеризовать структуру графа многогранника. В диссертации изучается задача упаковки шаров (коды на многогранниках). При этой задача рассматривается также и для случая, когда допускается пересечение шаров по сферам. Эти исследования тесно примыкают к задаче оценки 'комбинаторной изменчивости выпуклого-многогранника к различным деформациям, а также продиктованы ■ стремлением распространить идеи теории кодов, исправляющих ошибки, на комбинаторную теорию многогранников.

Далее в диссертации описаны собственно комбинаторно-метрические исследования выпуклого многогранника.

Теоремы единственности длй выпуклых многогранников, т-е. теоремы об однозначной определенности выпуклого многогранника с теми или иными параметрами в некоторых случаях по-' рождают практические" (эффективные) способы задания выпуклого многогранника.

В диссертации описывается, названный нами комбинаторно--метрическим^ способ однозначного с точностью до' движения и отражения задания многогранника. Такое двухуровневое задание многогранника описывается совокупностью . двух типов параметров? комбинаторным, каким является граф'многогранника (например, матрица инцидентности или смежности), и достаточным

числом метрических параметров . (например, тройки координат 'вершин, четверки коэффициентов линейных неравенств, расстояния между вершинами). При этом оценивается сложность (минимальное число метрических параметров) комбинаторно-метрического способа задания для каждого из перечисленных типов метрических.параметров.

Такой двухуровневый подход диктует новее направление исследования, глубже раскрывающих. природу самих многогранников, и дает возможность сократить число метрических параметров, достаточных для- однозначного задания многогранника. Следует откетить, что способ задания многогранника при услс-Еии известности его графа имеет также и практический интерес. Например, при вводе в память ЭВМ большой серии многогранников заланого комбинаторного .типа.

Дальнейшие исследования касаются вопросов, связанных с деформациями'выпуклых многогранников. Предлагается подход к изучению, выпуклого многогранника в динамике, т.е. изучается влияние.непрерывных деформаций многогранника на изменение комбинаторной структуры.деформируемого многогранника. Описываются типы деформация, продиктованные различными способами задания, выпуклого многогранника. Деформациям многогранник подвергается посредством изменения положения вершин или граней. При этой в зависимости от' рассмотрения . вида системы координат (декартова или. сферическая); от того какие параметры подвергаются изменениям, в каких пределах изменяются выделенный' параметры, порождаются различные типы деформаций. Устанавливаются взаимосвязи между различными типами деформаций.

Основные исследования направлены на изучение классов деформированных многогранников, порожденных от исходного многогранника (порождающего многогранника). Актуальность • рассмотрения классов деформированных многогранников заключается в том, что каждыя многогранник из такого класса оп-.ределябтея (в основном) порождающим хногограшш.'сом'и вектором--изменений своих параметров.. Здесь ' возникает вопрос - о перечислении.и подсчете комбинаторно различных многогранников, порождаемых от исходного многогранника при тех или иных типах деформаций. ■ .

■ Число различных комбинаторных типов многогранников, Порождаемых от исходного многогранника в результате . применения даиного типа деформаций рассматривается как мера комбинаторной изменчивости многогранника к этому типу . деформаций. Классы деформированных многогранников возникают при моделировании естественного процесса роста, минералов;изготовлении изделий многогранной формы й т.д.

Далее описывается специальный способ проектирования 3- • верного выпуклого тела на 2-мерную поверхность Ссферу или плоскость) - ^-проектирование. При этом- основная цель -исследований состоит в решении обратной, задачи, т.е. в определении параметров многогранника до его ^--проекция. Эти исследования, в свою очередь, порождают задачу изучения влияния изменений параметров многогранника на его г-проек-цию, что привадит к рассмотрению классов деформируемых мцо- ■ гограннйков. Практическая же ценность этих исследований в том, что ^-проекция моделирует лазерные рефлектограммы (специфическая картинка на экране, формируемая отражением и преломлением исходного плоско-параллельного лазерного потока ' от тела) прозрачных тел формы выпуклого многогранника. Э]й исследования приводят к задачам специального освещения ■ выпуклого, многогранника потоками параллельных лучей.' Изучаются задачи определения минимального числа потоков, ^ освещающих всю границу многогранника, устойчивого освещения . многогранника,

Метод ^-проектирования распространен ; также на неоднородные выпуклые многогранники и ставится задача восстановления таких многогранников.

^-проектирование и методы решения поставленных задач существенно отличаются от известных в литературе исследований по теневым, рентгеновским и другим типам проекция выпуклых тел.

И, наконец, в заключении приводятся приложения результатов диссертации к диагностике качества огранки бриллиантов, • бесконтактндиу измерению геометрических параметров алмазов и методу оптимального раскроя алмазов.

■ ■''■. Цод-ВайДО.. Исследование комбинаторной структуры выпук-; дого многогранника на базе синтеза графов многогранников от- .

носительно их "склппки'' и упаковки вароз в графе-многограшш-• ка. Описание и установление оценок сложности способов задания . выпуклого многогранника, базирующихся на графе многогранника. Рассмотрения классов деформированных выпуклых многогранников. Сравнительный анализ таких классов при различных типах деформация и получение результатов об их комбинаторной, мощности (число комбинаторно неэквивалентных многогранников). Изучение специального способа проектирования '■ (^.-проекции) выпуклого многогранника и решение обратной задачи - восстановление выпуклого многогранника по их. ^-нреейгшлм. ■ Прмсжонкл теоретических результатовпри рсагения задач, автоматизации я ептикимции технологического процесса огранки алмазов.

1&ИДЫ_В5Шдо.еа»1йДх 3 работе используются методы дискретной катекатики и математической кибернетики.

Научная новизна, Все основные постановки задач и. основные результаты диссертации являются новыми. В диссертации установлены, достижимые нижние и верхние оценки сложности синтеза произвольного трехсвязного пленарного графа, из базисных графов и разброса различных способов синтеза; описана последовательность графов многогранников с растущим числом вершйн, имеющих совершенные а-коды.; получены окончательные результаты о сложности кокбиНаторно-метрического задания выпуклого многогранника при типах метрических паракетроэ задания: Вершинном, граневом и расстояниями; описаны всё типы деформаций выпуклого многогранника, основанных; на различных способах его задания, выделены комбинаторно устойчивые к деформациям выпуклые многогранники, оценено максимальное значении комбинаторной мощности класса деформированных многогранннков при ограниченных деформациях выпуклого йкогогранкика с Г гранями; разработаны алгоритмический и аналитический йвтоды расчета ''-проекции выпуклого многогранника, сформулированы корректные постановки задачи определения ЕНпуклого многогранника по его р-лроекции, разработаны соответствусяие методы решения обратной задачи; описаны приложения полученных теоретических.результатов в задачах"оценки.качества, огранки . бриллиантов,. бесконтактного' ■■ измерения . геометрических . паракетров алмазов, оптикаяъного раскроя -алмазов.

з. Диссертация в основном носит теоретический характер. Подученные результаты . и разработанные, методы нашли свои применения, отраженные б приложениях диссертации. Они также могут найти применение в вычислительная геометрии, в теории оптимизации, в -минералогии, в оптике.

Дпробдцир работы. Результаты диссертации излагались ь Международном математическом центре им.' С.Банаха (Варшава, 1386),на Международном симпозиуме по теории информации (Москва-Ташкент, 1384), на Советско-Итальянском симпозиуме по некорректным и некраевым задачам математической физики (Самарканд, 1991),'на VII, уш,. IX Всесоюзных семинарах до теоретической кибернетике (Иркутск, 1985.; Горький, 1908; Волгоград, 1990), на I и П Всесоюзных семинара* по дискретной 'математике и ее приложениям (Москва, 1984, 130?), на Всесоюзной школе-по сложности управляющих систем (Новосибирск, 1989), на •'. IX Всесоюзной конференции по геометрии (Кишинев, .1908), Всесоюзном симпозиуме по вычислительной томографии (Ташкент, 1389), на первом геммологическом совещании (Черноголовка, 1905), ' на семинаре по кибернетике б МГУ, под руководством чл.-корр; РАН С.В.Яблонского, на семинарах по дискретной математике, в ИГУ, ' на семинарах по дискретной математике и ей. приложениям в , ТашГУ.

Цублщшш*. Основные результаты диссертации опубликованы в 17 работах, список которых приводится в- конце' автореферата. В совместных работах постановки задач, идеи решения и основные теоретические результаты, включ'енные в 'диссертацию, принадлежат диссертанту. Работы, освещающие приложения теоретических результатов, проведены совместно. "'

Структура и обьеи работы. Диссертация состоит из введения, пяти глав и списка "литературы. Первая'глава разбита на 2 параграфа, вторая - на г, третья - на 2, четвертая -, на 5, ' пятая на 3. Обьем работы 2Ц страниц. Список литературы содержит -92 наименования. -.■

. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ '

. Ш .аведеции приведена краткая история вопроса и; дан •

то

обзор основных результатов работы. ,

В парвоя главе содержатся предварительные сведения, используемые, в работе.

посвящена исследованиям комбинаторной структуры выпуклых многогранников, т.е. графов многогранников. - ,

.. .' В параграфе .2.1 иссдвдузтся алгебра графов нногогранни-ков на .основе рассмотрения операции .склейки таких графов. НэучЬннз направлено на выделение системы базисных графов многогранников л оценивание сложности синтеза произвольного графа 3-многогранника из базисных. Пусть б, к о, - трехевлзные лланарные графи, низшие грани и в, одинаковой степени, соответственно. Тогда, склейкой графов с, и б,, по граням • и (обозначается назовем тргзхсвязныя планарныя граф о, взр'зины п. ребра которого есть все вершины и ребра графов о, и а, при условии, что вершины я ребра. I рана 8, отокдсствля-ютея с сеттвегстпуюдаш верийиами к ребракя грани а,-. Естсст-езинни образом.определяется обратная операция ■ - расклейка 3-связного пленарного графя о на 3-связные пленарные графы б, к 6,. Трехсвяэныя планарнна граф, к кстороку нельзя применить операция расслейкн, называют элементарный. Элекентарнкз графи образует базис в классе Зтсвязиых пленарных графов относительно операции склейки графов. ■'

■ Получены следувдке результаты о количественных характз-. ристшсах щхн;<зссоз синтеза СсклсяюО и анализа (расклейки) ГрЕфОП многогранников.. .

ТЕОРЕМА 2.1. . Сложность синтеза произвольного

З-свяэлого планаркого графа О с Г гранями, т.е. мдкеихалыгое чнело. элвкентарных графов, из которых кокет быть склеен граф С(П, удовлетворяет неравенствам:

1 < 1^(0 < 1(Р-2)/23,'Г>4

ТЕОРЕМА 2.2. РазЬрос сложности у(С) синтеза графа многогранника с Г гранями, т.е. отнесение максимального числа ба-зкеинх графов, ■ из которых }«шзт . быть синтезирован граф <НГ), к инникуку этого "числа, удовлетворяет неравенствам: >

Г 1, 4 < Г < 7 1 < у(0) < 7(Г), где у<Г) •= {

Оба результата окончательны, т.е. для любого Г существуют примеры их достижимости.

Установлены ряд условия элементарности и критерия незле-иетарности графа выпуклого многогранника.

В параграфе 2.2 вводятся необходимые определения и обозначения, приводится постановка задачи об упаковка и формулируются результаты.

•' Система шаров на графе многогранника, которые могут пересекаться между собой не более, чем на своих сферах, называется упаковкой шаров. В скучна, когда любая вершина графа принадлежит некоторому шару, упаковка называется плотной.

Подмножество вершин графа многогранника, находящихся друг от друга на расстоянии не меньше, чем <1 назовем а-кодом. Очевидно, что й-код порождает упаковку шаров радиуса 1(3/21 на графе многогранника. В случае, когда эта упаковка является плотной, код назовем совершенным.

Установлены следующие.результаты.

ТЕОРЕМА 2;з. Для любого натурального а, й >2, существует последовательность многопшшиков с растущим числом вер-йин, ИйеЮщИх совершенные и-коды.

Приводятся описания многогранников, имеющих совершенные а-кодц; -

Л Е; М М А. Максимальное - значение мощности 2-кода 'в 5 классе графов многогранников с В вершинами равно 1(2В~4>31.

ТЕОРЕМА 2.5. Существует последовательность гра^в многогранников с числом вершин В, которые имеют два различных А-кода (а - фиксированное) с отношением мощностей к(в,с1) порядка В. В частности при а~2:

11 2.4

. В - < К1В.2) С -3- В -

Третья глава посвящена комбинаторно-метрическим исследованиям выпуклого многогранника, продиктованым рассмотрением 1 изучением многогранника в как графа, на котором заданы значения его метрических параметров.

В параграфе 3.1 исследуется задача сложности задания выпуклого многогранника в к3 при условии, когда известен граф многогранника (комбинаторный тип многогранника). Способ зада нкя выпуклого многогранника как графа, на котором определены

значения метрических параметров, назван конбинаторно-метриче-скин. В качестве метрических параметров рассматриваются еле-' душке варианты:

D трояка декартовых координат, определяющая положение вершины многогранника; . '

Z) четверка коэффициентов линейного . уравнения, определяющая положение плоскости грани Сэтот случай двойственен случаю 1)) многогранника;

3) расстояние между Есршинами.

Нетрудно убедиться, что для однозначного задания выпуклого многегранника в к* при условии отсутствия дополнительных сведений требуются в случаях 1) и Z) параметры всех В вершин и Г плоскостей граней, соответственно, в случае 3) - ЗВ-Б

расстояний из числа всевозможных ["] расстояний.

Теперь, если предварительно известен граф выпуклого многогранника, то может возникнуть избыточность информации в определении многогранника. Таким образом, возникает задача об отыскании минимального числа метрических параметров, по которым однозначно определяется исходный многогранник.

Получены следующие результаты.

ТЕОРЕМА 3.1. Пусть L,(M(P)). - минимальное число расстояния между вершинами, W которым однозначно определяется выпуклый многогранник MCP) с Р ребрами при условии, когда известен его граф. Тогда

умер» = р.

Разработан алгоритм подбора тех Р расстояния, с помощью которых рдиезначно определяется И с данным графом.

ТЕОРЕМА 3-Е. Пусть 1^(11 (В)) - минимальное . число

вершин, метрические параметры которых однозначно определяют выпуклый многогранник М(В) с В вершинами при условии, когда известен его граф. Тогда

2 + 2 с Lt(MCBfl св. ; -

Из принципа двойственности следует, что минимальное число ь,(й(П) плоскостей граней, метрические параметры ко--торых однозначно определяют выпуклый многогранник М(Г) с. Г

гранями при условии, когда известен его граф .

Г

2 + 2 с 1,(МСГ}) < Г.

Отметим, что оценки обоих результатов достижимы.

В параграфе 3.2 исследуется вопрос "устойчивости" .комбинаторной структуры (т.е.грас^) выпуклого >щогогранника М к изменениям тех иди иных метрических параметров цно-гогранника 1!. Приводятся определения различных типов деформация многогранника и устанавливаются взаимосвязи • нейду

ними. ' 1 '

Пусть выпуклый'многогранник Ы' получен от выпуклого многогранника У путем изменения его некоторых метрических параметров. Тогда многогранник И' называется деформированным многогранником, порожденным от исходного многогранника У. Класс всех выпуклых многогранников, порожденных'от исходного выпуклого, многогранника Ы путем изменений его выделенных метрических параметров обозначим через и СМ). Число комбинаторно-неэквивалентных выпуклых многогранников в п. СМ) будем рассматривать как меру Комбинаторной изменчивости исходного многогранника, М. Целью исследования является задача подсчета и . перечисления комбинаторно-различных многогранников в Класср и см).

Далее приведем определения рассматриваемых типов деформаций:

Пусть многогранник Ц с В вершинами и Г гранями задан системой линейных неравенств, не имеющей избыточных неравенств, или координатами вершин в сферической системе координат. ..Изменение лишь, линейных (линейных и услоаих) параметров граней многогранника и, пр,н котором система, соответствующая измененному многограннику, является совместной и никакое . неравенство этой систем не окажется .избыточный, называете? линейно-ограниченной деформацией или ЛОД (линейно-угловой ограниченной деформацией млн ЛУОД).

Линейна-угловая ограниченная деформация многогранника11, при которой сохраняются смежности граней по ребру, наливается , ограниченной деформацией или ОД. • ' "

Изменение лишь полярных радиусов (полярных радиусов к

угловых параметров) вершин многогранника Н с В вершинами, при котором существует В-вершннная выпуклая оболочка порожденных вершин, и начало системы координат является внутренней тонкой,- называется полярно ограниченной деформацией или ПОД Сполирно-угловоя ограниченной деформацией или ПУОД).

Колярно-угдовая ограниченная деформация многогранника М, при которой сохраняются смежности вершин по ребру, называется сферически ограниченная дефорнг.циея или СОД.

Пусть Н? есть многогранник, двойственный к многограннику К.

• ТЕОРЕМА 3.3. Для каждого шгогограНишса кз класса

СИ.ЛУОД) в класса я (М*,ПУ0Д) существует двойственный ему многогранник . и, наоборот, то - есть двойственные многогранники М и •Н".двойственны относительно ЛУОД и ПУОД.

СЛЕДСТВИЕ. Класс ^Н,ЛУОД) содержит все яногограшши с Г гранями.

Унсгогранник,' порожденный от ^угольной пирамиды Ц некоторой деформацией типа ЛОД или ОД СПОД млн СОД), называется обобщенным клином (ломаной пирамидой).

ЛЕММА 3.6. 1;-угольная пирамида М1 является порождающим

многогранника« для класса ^ СН1(ЛОД) и и СМ^ПОД).

Пусть а (В,Г) - класс комбинаторно различных ымгагран-ннков с В вершинами и Г гранями,

'• ' ТЕОРЕМА 3.4. Любой многогранник ио"класса из и СВ.ГХ кс^б:шатсряо неэквивалентный (В-1)-угольной пирамиде, 'порождается либо от. некоторого многогранника из класса и СВ-1,Г) пссрздстьом ОД, либо от некоторого многогранника из класса я-СЙД'-П посредством СОД.

На основе вышеизложенных результатов разработаны алго-рнтиц для причисления всех комбинаторно различных многогранников с В вершинами (Г гранями), а тагае комбинаторно различных многогранников из различных классов ' не-формированных ккогогранников.

.Описаны также классы многогранников, д.та которых lr.tU.U8i) |=г, т.е. классы комбинаторно нензненчнььх мюгог-. -ранииков. Из теорем 3.5-3.9 вытекает следующая

- , ТЕОРЕМА. Класс комбинаторно неизненчнвыя .иншпгршгаахоз

13 относительно ОД ССОД) совпадает с классом всех простых Ссимплициальных) многогранников ;

2) относительно ЛОД (ПОД) является классом всех простых (симллициальных) порождающих для ЛОД (ПОД) нногограннн-

. ков, не имеющих линейно (полярно) зависимых вершин (граней) ;

3) относительно ЛУОД (ПУОД) состоит из единственного многогранника, комбинаторно эквивалентного тетраэдру..

Показано также, что максимальное значение меры комбинаторной изменчивости выпуклого многогранника с р гранями и п вершинами при деформациях типа ОД и СОД соответственно имеет •экспоненциальный рост (теорема 3.10).

Четвертая глава посвящена изложению результатов исследований по специальной проекции выпуклого многогранника на экран (2-мерную поверхность (плоскость, сферу)) - ¡^-проекции. При этом основная задача состоит в решении обратной задачи, т.е. в опроделенин параметров многогранника по его р-проекции...

В параграфе 4.1 вводится понятие ^-проекции, приводятся ее основные свойства.

Пусть в трехмерном евклидовом пространстве <*" в некотором фиксированном направлении'задан поток П плоско-параллельных лучей. В направлении потока расположен выпуклый многогранник М, который определен своими геометрическими параметрами и некоторым (физическим) "параметром п>0, определяющим показатель преломления многогранника М. Грань Г многогранника М освещается потоком П параллельных лучей с

направлением 1, если (КД)>о, где N - внутренняя нормаль грани г.

При ¡¿-проектировании каждый луч при пересечении с гранью формирует отраженный и преломленный лучи согласно правилам:

- угол а между падающим лучом и нормалью грани (угол падения) равен углу Р между отраженным лучом и нормалью (угол отражения).

- угол г между преломленным лучоя и нормалью граня (угол .преломления) определяется по следующим формулам (1):

г агсз1п( ± в1па), если пад-й.луч иап. из «3\й вы

X — ' '

1 а1'сз1п(пз1па), если пад-Я.луч нап.из м в ка\м

Рассмотрим сферу Б, которая помещает в себя выпуклый', многогранник М и находится от него на некотором расстоянии О-Св метрике Хаусдорфа). Зафиксируем точки пересечения Сточки отражения) выходящих из М лучей со сферой 5. Множества всех точек отражения на сфере Б образует ^-проекцию многогранника Н при освещении потоком П Сстрогое определение приводится в % 1 главы 4). Пусть все грани М пронумерованы, тогда каждому выходящему лучу можно сопоставить след - последовательность номеров М, участвующих . в формировании выходящего луча. Множество всех точек ^-проекции, имеющих одинаковый след, назовем рефлексом. Порядок точек рефлекса определяется длиноя соответствующего следа. Множество всех точек отражения от многогранника М до Н-го порядка, порождаемое исходным потоком П, определяет ^-проекции порядка многогранника И.

Установлены следующие положения о «"-проекциях выпуклых многогранников.

1) Пусть задана ^-проекция выпуклого многогранника И на сфере радиуса г ( в частности на плоскости, находящейся на расстоянии й от многогранника), и направления потоков выходящих из и лучей попарно различны, т.е. нет параллельных выходящих потоков. Тогда существует такое значение г0 (соответственно ао), что при увеличении г, г>го {й.ах^ ), расстояние между рефлексами увеличивается, а формы и параметры рефлексов не меняются, т.е. сохраняются угловые параметры точек рефлекса в сферической системе координат (соответственно в декартовой системе координат), которыми однозначно определяются точки рефиекса на сфере фиксированного радиуса (на плоскости, находящейся на фиксированном расстоянии от многогранника).

2) Погрешность определения угловых параметров граней выпуклого многогранника по направлениям лишь выходящих потоков стремится к нулю при г -■>- ^ (с1 где г - радиус' сферы' экрана М - расстояние от плоскости до многогранника). Па этой основана актуальность рассмотрения так называет!

точечной p-прсскции, когда каждый рефлекс заменяется некоторой точкой этого рефлекса.

В параграфе 4.2 приводятся различные постановки обратной задачи, т.е. задачи восстановления Выпуклого многогранника по его ^-проекции.

1) Обратная задача в общей постановке .состоит в определении параметров задания выпуклого многогранника по значениям параметров его р-проекции или семейства ^-проекций в различных направлениях. .

2) Объединение двух р-проекций 1-го порядка, порожденных двумя противоположно направленными потоками, освещающими все грани многогранника/ будем называть объединенной Р'-проекцивй 1-го порядка.

Обратная задача состоит в определении параметров задания выпуклого многогранника по его объединенной »'-проекции первого порядка.

3) В случае if-проекции N-порядка предлагается следующая постановка обратной задачи. Пусть задан сыпуклый кногограниик 1.1 и его некоторая ^-проекция Р(Ю такие, что по РСШ многогранник М восстанавливается однозначно, то есть якобиан системы уравнений . ; • ' .

отличен от нуля, где xJ - вектор параметров, определя&щия J-b грань многогранника, - вектор параметров, определяющий 1-й точечный рефлекс ^-проекции' многогранника. Пусть и ffi,p,«) -класс деформированных выпуклых многогранников, порождаемых от выпуклого многогранника М посредством- линейно-угловых ограниченных деформаций, при которых линейные параметры независимо изменяются на величину не более р и углов® - не более «, при этон ри а считаются "достаточно :иалымй", т.е. существенно меньшими относительно значений : лннзйиых параметров граней и двугранных углов. .Пусть известными являются параметры некоторого-. выпуклого ккогог^аинкка И Сбудем называть его идеальным многогранником)'и параметры его', «•-проекции Р(Ю (которые определяются, например, с помоев алгоритмов реаенйя прямой- -задачи).-. Пусть некоторой, , так называемый,, реальный киогогргшшк• М 'с %..(»,р,«')' и известны

координат era ^-проекции PCM') (¡»'-проекцию реального многогранника на практике можно.рассчитывать на приборе. В этом случае, естественно, .неизвестной остается система следов.). Задача заключается в - определении параметров многогранника М' по-параметрам Ы.'Р(Ю и РОГ).

• 4) Пусть М(Г,п) - (однородный 3-шюгограшшк) З-многог-ранник с Г гранями и показателем преломления п. Однородный 3-многогранник НСГ.п), содержащий семейство из к (к il ) попарно непересекающихся .однородных шаров с- показателен преломления nt, n^n, назовем неоднородным 3-многограшшкои. Естественным образом обратная задача ^-проектирования распространяется на неоднородные выпуклые многогранники. Задача состоит в восстановлении внутренней неоднородности выпуклого многогранника по его tp-проекции. В диссертации исследуется, задача " восстановления неоднородного выпуклого многогранника при следующем, имеющем практическое значение, упрощении. При этом, если при попадании' луча на грань многогранника он порождает отраженный и преломленный лучи, то при попадании луча .на поверхность" шара принимается, что не порождается ни отраженного, ни преломленного луча (т.е. луч, как бы, "выходит из игры").' Таким образом, отличие ^-проекции неоднородного многогранника от соответствующего однородного многогранника заключается только в тон, что " каждый рефлекс первого, ' .как множество точек, является подмножеством соотвгпствующего рефлекса второго,, т.е» может происходить полное или-частичное "затмение." рефлекса.

В параграфе 4.3 излагаются результаты, относящиеся к прямой задаче. В общей постановке прямая задача состоит- в определении параметров ^-проекции по параметрам задании выпуклого многогранника и параметрам проектирующего потока и экрана. Нетрудно убедиться, что пряная задача в общем случае (постановке) некорректна, а именно; возможны малые изменения угловых • параметров граней многогранника, приводящие к значительным изменениям положения рефлексов (Т.е. не выполняется требование устойчивости корректной постановки задачи).

В диссертации приводятся различные алгоритмические решения • прямой- -задачи. Разработаны алгоритмы построения

р-проекцкк н-порядка выпуклого' многогранника. Разработан также аналитический метод определения . дискретной (вместо непрерывного потока рассматривается дискретный пучок лучей) р-проекции выпуклого многогранника. При этом приведен явный вид уравнения, связывающего направление выходящего потока с .угловыми и линейными ■ параметрами граней многогранника с номерами 1,,!^, ...,1М и параметрами соответствующего

падающего луча. С другой стороны, направление выходящего потока однозначно определяется по координатам произвольных трех вершин рефлекса ^-проекции, имеющего след

Для написания же системы уравнения (очевидно, конечной, т.к. число уравнений равно числу рефлексов ^-проекции), связывающей параметры т рефлексов сг-проекции с параметрами х исходного многогранника, предложена матричная форма

• • I - -(«}'/

Отметим, что эта система уравнения $ общем' виде является нелинейной. Вместе с тен, матрица А икеет вид:

1 * V V......V ,

М М-1 I I

где V. - квадратная матрица 4-го порядка, зависящая только от параметров грани с номером

В параграфе 4.4 рассматривается задача об освещаемости всех граней выпуклого многогранника,. " независимо от расположения потоков параллельных лучей.п'ро диктованная решением обратной задачи '.Р-проектирования. - Исследуется также задача о диапазоне изменения направления падающих потоков, в пределах которого остаются освещенными все грани многогранника И выборе, "оптимального" направления освещения.

В этом направлении получены следующие результаты.

1. Существуют два взаимно противоположных потока , параллельных лучеЯ, в совокупности _ освещающих всю границу произвольного заданного^многогранника М. ■ .% Л . , 2.. Минимальное. чдеяо фиксированныхнаправлений -потоков. параллельных лучей, :освеаавй\их вса границу многогранника при любом-его располокений,^вно 4. , . .

В параграфе 4.5 описываются методы решения обратной за-

?.оу

дачи, т.е.' задачи восстановления выпуклого многогранника по его ip-проекции.

УТВЕРЖДЕНИЕ 4.6. Обратная задача в общей постановке является некорректной, существуют примеры неоднозначного определения выпуклого многогранника по его [Р-прсёкции.

ТЕОРЕМА 4.4. Произвольный выпуклый многогранник по его. объединенной г-проекции 1-го порядка на. сферу конечного радиуса определяется однозначно.

Предлагается- алгоритм нахождения параметров .'выпуклого' многогранника по его объединенной г-проекцми 1-го порядка на сферу.

Два выпуклых многогранника И, и Нг называются (р,^-соизмеримыми, если существует такое ' их расположение относительно системы координат'и. между-.. их гранями - ложно установить взаимно-однозначной соответствие, что. линейные. параметры соответствующих граней отличаются не более чек на р, а угловые - не более ' ■ "

Пусть U - некоторый выпуклый' многогранник и РСМ)- - его некоторая точечная ^-проекция на плоский экран, находящийся на расстоянии D от 11 и минимальное расстояние между точками - ■ рефлексами равно d. Пусть К' - выпуклый многогранник из а Ш.Р,«) и РСМ') - его точечная if-проекция на тот же экран, находящийся также на расстоянии D от И', ^проекции Pili) и РСМ') называются соизмеримыми с РСМ), если существует движение РСМ') (рассматриваемое как движение цельной-фигуры), при котором можно установить взаимно-однозначное соответствие между точками РСМ) и Р(И'), что расстояние незду соответствующими точками строго меньше й/г. .

ТЕОРЕМА 4.5. Если многогранник М-'- е w (М,р,а) и р-проек-ция РСМ*) соизмерима с РСМ), .то многогранники М и .'И* (р,а)~соизмеримы и при подходящем подборе р, <* системы следов их рефлексов совпадают, т.е. сопоставленные рефлексы имеют одинаковый след.

ТЕОРЕМА 4.6. Пусть выпуклый многогранник И однозначно определяется по Р(И) и !!' ея (М,Р,а).' Если I'd"), соизмерима с РСМ), то при подходящем выборе р, а задача определения выпуклого многогранника ¡I1 по М, .РШ), РШ')" явллсяся корректной, т.е. существует единственное и■ устспчакоа решение

обратной задачи.

.Таким образом, метод определения параметров многогранника м* е in (М.р.а) сводится к подстановке парапетов его Дискретной ^-проекции в левую часть системы С) и ее решению. При этом вопрос о .том,'параметры каких рефлексов, из- РСМ') следует подставить в какое уравнение из системы (*), решается на основе соизмеримости г--проекций РСМ) и Р(М'). Суть метода заключается в распространении однозначной восстанавливаемости наперед заданного многогранника М для восстановления неизвестного многогранника М' из класса w СМ,",«). При . этом "работоспособность" метода определяется величинами р, о, которые задают широту класса m СМ,р,а); В диссертации приведены примеры эффективного использования этого-метода в решении задач, имеющих важное прикладное значение.

Предлагается метод приближенного восстановления параметров неоднородного выпуклого многогранника по его. г-проек-ции.. Этот метод сводится к решению некоторой системы булевых уравнений. Дается критерий однозначного приближенного восстановления паранетров неоднородного 3-многограниика по его ^-проекции. •

В пятой главе описываются приложения результатов диссертации. В параграфе' 5.1 предлагается методика классификации-бриллиантов на основе их лазерных рефлектограмн, которая позволяет оценивать качество огранки бриллиантов. ;'.

В параграфе 5.2 описан математический метод' ■ восстановления угловых и линейных параметров сырья-алмаза октаэдральной формы по его лазерной рефлектограиме. • :

В параграфе 5.3 описан некоторый подход к решению задачи оптимального раскроя. Этот подход- основывается на . понятии порождающего многогранника, т.е. решается конкретная задача оптимального раскроя из; сырья' формы . порождающего, многогранника М .и изучается влияние дефорхац'ий многогранника' М на решение задачи; .,.'..■• Л .

Задача оптимального раскроя решается для случая, • когда формы изделия фиксированы", а размеры изделий могут'меняться в определенных рамках' . ;.В этом случай • решается задача-максимизации объема выхода годного изделия'. . Разработан комбинатсрно-геонетгшческия . метод- ' оптимального раскроя;

кристалла алмаза. При этом кристаллы бездефектного алмаза моделируются многогранниками из класса я (Н.ЛОД), где U -октаэдр. Бриллианты круглой или фантазийной формы, 'выпускаемые в производстве, моделируются многогранниками из класса я (м,0Д), где многогранники М соответствуют эталонным бриллиантам данной формы.

Следует отметить, что предложенные методы раскроя алмазов внедрены в практику.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Установлены достижимые .верхние и нижние оценки сложности синтеза и разброса различных способов синтеза графов выпуклых многогранников из элементарных таких графов.

2. Построены и оценены мощности Сп,ф-кодов на графах выпуклых многогранников.

3. Разработан комбинаторно-метрический способ задания выпуклого многогранника и оценена его сложность.

4. Описаны и сравнительно анализированы классы деформированных многогранников при различных типах деформаций. Выделены комбинаторно кеизмещивые и имеющие экспоненциальную меру изменчивости выпуклые 'многогранники.

5. Изучена ^-проекция выпуклого многогранника. Установлены результаты и на их основе разработаны методы однозначного и устойчивого восстановления выпуклого многогранника по его р-проекциям.

ОСНОВНЫЕ УАТЕРИАЛЫ ДИССЕРТАЦИЙ ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

1. Абдурахманоа К., Пулатов А.К. Конструкция ' совзр-сениых кодов выпуклых многогранников. - Методы дискретного анализа в решении экстремальных задач. - Новосибирск, 1990. -Вып. 50- - С. 3-9.

2. Мамасандов ¡i.A., Пулатов А .(С. и др.- Разработка алгоритмов специального кодирования и восстановления выпуклых нногогранников. - Отчет по госбюджетной работе, н . Гсс. регистрации 01В600ВН71, 1953.-' ."

3. Пулатов А.К. К структуре плотно упакованных кодов. -Методы дискретного анализа в теории кодов и

схем.. - Новосибирск, 1976, - Вып. 29, С.

4. Пулатов А.К. К комбинаторной теории выпуклых многогранников. Тез. докл. 9 Всесоюз. геом. конф. - Кишинев, 198В. - П. 260-261 .

5. Пулатов Л.К. п'-проекции и их использование в задании выпуклых многогранников. - Тез. докл. Б Межд. Симпозиума по теории информации. - Москва-Ташкент, 1384.- с. 154 - 155.

6. Пулатов А.К. О некоторых комбинаторных задачах на выпуклых многогранниках ^ Тез.докл. 7 Всесоюз. конф. по проблемам теоретической кибернетики, Иркутск, сент, 1985 г. -Иркутск, 1305. - С.1Б9-170.

7. Пулатов А.К. О задаче определения выпуклого многогранника по его ^-проекции (лазерной рефлектограмме}. - Тез. докл. Советско-Итальянского симпозиума, Самарканд, 1390.

8. Пулатов А.К. ^-проекции многогранника и исследование обратной задачи. - Материалы Всесоюз. семинара по дискрет, математике и ее приложениям. - М., МГУ, 1987.

9. Пулатов А.К. Р-проекция многогранника и исследование обратной задачи.---'' Труды И ■ Всесоюзного семинара по дискретной математике и ее приложением,- Москва, 1909.- С. 253 - 259.

10. Пулатов А.К., Битюцкая Н.И. Синтез и сложность графов многогранников на основе операции склейка. - Сб.: Перманенты и ее приложения, Красноярск, 1991. --в.- 53-64.'

И. Пулатов А.К., Махкамова MX, Рахманова Э; Математическая модель принципа лазерной рефлектоскопии. - Изв. АН ■ УзССР, СТН. - N2. - 1S8B. - 0. 65-67.

12. Пулатов А.К., Саматова Н.Ф. О сложности задания, выпуклого многогранника в к". - Дискр. мат., том 3, вып. 2, 1391. - С. 148-156.

13. Пулатов А.К., Султанов Д.А. Аналитический метод определения дискретной ¡р-лроекции выпуклого многогранника в Рук. деп. в УэНИИНТИ. - Ташкент, 1991. N 181. - Уз.

- 14 с.

14. Пулатов А.К., Шамуилов Б.Я. Задача восстановления неоднородного выпуклого многогранника б по его ¡р-проэкш.ш.

- Изв. Вузов. Математика, 1990. - 5(336). - с. 84-86.

15. Пулатов А.К., Хужасв Т.Х. О комбинаторной структуре и - мощности классов деформируемых многогранников. Вероятностные методы и кибернетика, Казань, выл. 24, 1390.

16. Пулатов А.К., Хунаев Т.Х. Об одном подходе к решении задачи оптимального раскроя. Рук. деп. в УзНИИНТИ. - Ташкент, 1991. - N 207 - 10 с.

Саматова Н.Ф., Пулатов АХ Сценка меры комбинаторной изменчивости выпуклого многогранника при ограниченных деформациях. Рук. деп. в ГФНТИ ГКНТ РУз. -Ташкент, 1993. - N 1799 - Уз.ЭЗ. - 12 с.

~ "/¿7.(

р. — Подписано к печати j9.O5.-03г. 8ак.—Ш-^З/ Тираж 1993 т.ОЬ 4п л

Отпечатано в АП ТПК

Ташкент, Навои, 30.