Геометрические минимальные остовные деревья тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ЬД С ь 3 2

Академия наук Беларуси Институт математики

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

Беспамятных Сергей Николаевич

ГЕОМЕТРИЧЕСКИЕ МИНИМАЬНЫЕ ОСГОВНЫЕ ДЕРЕВЬЯ 01.01.09 - ыатеыатическая кибернетика.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Минск - 1992

Работа выполнена в Уральском госуниверситете

Научные руководители. - кандидат физиковматематических наук

дсцент Яковлев Николай Николаевич

- кандидат $нзико-матеыатичес:шх наук ' Корнеэнко Николай Михайлович

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

Метельский Николай Николаевич

- кандидат фкзико-матекатическик паук ЕайнштеЯн Александр Давидович

Ведущая организация, , - Институт математики и юхшшки

Уральского отделения АН России С г.Екатеринбург )

Защита состоится " 22" _1932 г. в час.

на заседании специализированного совета К 006.19.01 в Иастс туте математики АН Беларуси по адресу: 220604, г. ¡¿иск, ул. Сурганова, 11, Институт математики АН Беларуси.

С дшзртац"еЯ можно -чзнахсукться в йийллотаке Илсти.у! математики АН Беларуси.

Автореферат разослан " 19." п3 1992 г.

Учений секретарь специализированного совета;

кандидат i*m. -мат. наук atik'-i-A-J^-j— д. Астровский

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

Актуальность- теми. Нахождение минимальных :товних деревьев являе.ся классической задачей дискретной тгиыизации. Геометрические миикыальнне остовные деревья троятся для полного графа, вершинами которого являотся точка -мерного пространства, и вес каждого ребра равен расстоянии гаду точками в некоторой метрике Минковского. Исследование ¿числительных аспектов задачи построения геометрических мимальных остовных деревьев составляет один иэ разделов ¡числительной геометрии 'Геометрические минимальные уговные деревья используются в иерархическом кластерном шлизе распознавания образов, в автоматизированном юектнровании микроэлектронноя аппаратуры и т.д. В (ссертации такке исследуются задачи построения остовных феььев минимального диаметра и вычисления модальности югоугольников.

Цель работы. Исследовать задачи построения геог ;трических минимальных остовных деревьев, построения остов-ж деревьев иинимального диаметра и вычисления модальности югоугольников. Разработать математический аппарат для пост-юния алгоритмов решения этих задач.

Научная новизна.

1. Обоснован региональный подход для построения геомет-гческах минимальных остовных деревьев в пространстве 05*. ла общая конструкция узких регионов в пространстве И^. При-¡дена верхняя оценка числа узких регионов. Для пространств зыерности к£6 даны конструкции регионов с меньшим числом тионов Разработан алгоритм построения геометрических мшг-льных остовных деревьев в пространстве

2. Для пространств доказана теорема, которая свяэива-: построение узких регионов с триангуляцией Ск-1)-мерного 6а. Для триангуляции к-ыерного куба предложен жадный метод, торий позволяет. почти вдвое сократить число регионов.

3. Разработан алгоритм нахождения остовного дерева мини-

Трепарата Ф., Шеймос И.. Вычислительная геометрия Вводе--ние /У М.: Мир, 1989.

- 3 -

мального диаметра для пространств О? и Доказано, что ;

горитм имеет временнуо сложность ОС. пЫодтй, где п - чк< точек.

4. Разработан алгоритм вычисления модальности выпукл: многоугольника, временная сложность которого оценивает ОС alода), где а - число вершин многоугольника. Для вычислен модальностей всех вершин выпуклого многоугольника привел алгоритм такой zs временной сложности. Доказано, что QCriloc является нижней оценкой времени вычислений модальности вьгп) лого многоугольника.

5. Разработан алгоритм вычисления модальности простого многоугольника, временная сложность которого оценивает ОСпа logn), где а =2-1одГгд+17 % 1-41. Лл.т вычислен модальностей всех вершин простого кногоугольшка привод алгоритм сложности ОСпсЗ, где с=1од(-*5*1Э ^ 1.695.

Практическая ценность. Результаты диссертация могут бить использованы в научных последовали по вычислительной геометрии, а также при разработке сгтг размещения, тр дссирозки, редактирования печатных плат,. -SK СБИС.

Публикаций и апробация. Основныо р зультаты диссертации опубликованы в работах С1—S3 и доклад вались на Всесоганой конференции по дискретной оптимизации Новосибирске, на семинаре Александрова б МГУ, на семинара;: математической кибернетике в _ Институте математики а Минск на семинарах кафедры математического анализа и.теории функц и на семинарах лаборатории математических методов и САПР Р Уральского госуниверситета.

Структура и объем работ Диссертация состоит из введения, трех глав, списка литерату ры, включающего 39 наименований. В диссертации содержится 2 рисунка. Общий объем - 111 страниц машинописного текста.

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

Во введении обосновывается актуальность исследований, i новизна и дается краткий обзор результатов, полученных диссертации.

Раздел 2 посвящен изучению геометрических ышималыи остовных деревьев и алгоритмов их построения.

Нахождение минимальных остовных деревьев является к:.ас-ическоЯ задачей дискретной оптимизации. - Рассмотрим неорнен-ированний связный граф б~СУ-,Е) с взвешенными ребрами. М и -иыальиыи остоинии деревом для графа называется остовное дерево с минимальным суммарным весом ейер. Геометрические минимальные остовние де-евья • рассматриваются для случая, когда ИЗР^ п Б - полный раф, в котором вес кахдого ребра равен с/Си,и), где и,ьеУ, С и, и) - расстояние кехду точками в определенной метрике. <5ычно пспользуг)тся метрики Минковского £.р, р21 и 1К, для оторих к

<1 си.име |и1-«||р),/р и

1 л

с1в(ц,и)*гсах( |и -и |, для ¿=1,2,... , М).

На рис. 1 приведено сравнение алгоритмов построения мн-имальных остовних деревьев, полученных в диссертации, с эвестнши алгоритмами.

Построение минимальных остовных деревьев в пространстве (Г^

Мир Предыдущий результат Оценка времени и памяти Новая оценка

1. р=а *>3 0С2к&!пС 1да)к"г1д1да) ОС2кп) ОС2кМ! аС1да)к~*1д1да) ОС/т)

2. р=1 к=3,4 ОСпС 1дп)к"81д1да) ОСп) См) ОСа(1да)к-г1д1да] • ОС а)

3. р=1 Ь=5 0(пС1дпЗ*1д1да) осп: ОС пС 1дгг)э 1д1дп.Э ^ ОСп)

4. р=1 М>5 0(п(21да)к1д1дп) ОСка) 1») ОС8кпС1да)к*г1д1да\ ОСкп)

Рис. 1.

«Э Унифицированный алгоритм.

Б разделе 2.1 даны основныэ определения и доказан теоремы, обосновывающие региональный подход.

Пусть х - некоторая точка из К* и B=ibJ> - сЗази пространства Регионом для точки х и базиса

к

называется множество RCВ,хЗ=(х+£ X Ь } X 20, Ь <В). Точка

i=i 1 называется началом региона.

Регион является переселением к полупространств. Регко является неограниченным выпуклым многогранником.

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

Пусть х - некоторая точка из и fi=(bJ) - бгои< пространства » т. - выделенный индекс иэ множеств; {1,2,... ,/?>. Полуоткрытым регионом для

к

точка х и базиса В называется множество RCD,x,n)={xi-r Xh

1« 1 1

X, 20, Ь.еВ для pcex i и X >0>. Точка х называется нач~ло?

XI Д1

региона.

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

В частности рассиатриьать • открытые рзгионы ix+j^ Л Ь j X >0,

i si

b еЮ, Однако для построения эффективных алгоритмов достаточно, как правило, одного индекса т, для которого неравенство из определения региона является стрЪгим. В дальнейшем под регионом, если не оговаривается специально, ш 'будем понимать как замкнутый так и полуоткрытый регион. Заметим, что полуоткрытый регион отличается от замкнутого региона тем, что грань региона, не содеркащая точку х*Ьт искяичаэтся из региона.

Для построения минимальных остойных деревьев представляет интерес так называемые узкие регионы. Регион R С замкнутый или полуоткрытый Э с началом; в точке х называется у з к й и, если он удовлетворяет следующему свойству

у y.zeFsix} dCy.zXmoxidEx.jO.dCx,гЭ> (i)

йемиа 2.1. Пусть и, и в w - точки из заданного множества V и dCu,w)>i7wx<dcu,ii),dCu,uD). Тогда любое минимальное остоз-ное дерево для вершин V не содержит ребро (и,и>).

Пусть Л - регион с началом в точке иеУ. Р е г и о -а л ь н ы м соседом для точки V называется точка и з региона £\<и> такая, что ¿Си,и)=т1п(сКи,и} (шбУпКчШ).

Доказано, что минимальное остовное дерево может содер-ать не более одного ребра (и,и) из узкого региона К. При том точка и должна быть региональным соседом для и.

Задача нахождения региональных соседей формулируется ледурщим образом. Даны множество точек V в ^-мерном прост-анстве и базис В пространства К* С для полуоткрытого егиона необходим еце выделенный индекс я 3. Для каждой точки из V найти регионального соседа С если он существует ) в егионе с началом в точке и и базисом В С Обозначим КС3,и) -айкнутый регион и КСЙ.и.т) - полуоткрытый регион

Чтобы свести задачу построения минимального остовного ерева к задаче нахождения региональных соседей необходимо остроить покрывавший набор регионоз [33 с началом в начале оординат, т.е. построить регионы К. такие, что

n . ' _ь

ьй^Ш" С для полуоткрытых регионов 1 и =5г\<0} ). Тогда ешив задачу региональных соседей для N регионов, мы опреде-им ребра, содерхааде минимальное остовное дерево. Число та-их ребер не превосходит А/а, где N зависит лишь от размернос-и пространства к и метрики но не зависит от числа точек, олученные ребра определяют граф б=(У,£), содержащий ыини-альноо остовное дерево. Для построения минимального остовно-о дерева теперь можно использовать любой из известных графо-ых алгоритмов. Следующая теорема утверждает редукцию задачи инимального остовного дерева к задаче региональных соседей.

Теорема 2.1. Пусть 3 - покрываоишй набор узких регионов пространстве (¡5* и / - п точек из Ребра, полученные в езультате решения задачи региональных соседей для всех реги-нов из 8, содержат минимальное остовное дерево для V.

Существование покрывающего набора узких регионов в ространствах большей размерности впервые доказал Яо Его онструкция основана на барицентрическом разбиении. После того возник вопрос о минимальном числе таких регионов. "Зоз-ачим минимальное число таких регионов для пространства -Для плоскости N'<8 С-рис. 3 5. Хотя для Евклидовой метри*-и на плоскости Иа=б С рис. 4 ).

Существование покрывающего набора узки* регионов доказывает, что степени вершин минимального уставного дерева для точек из пространства 05* ограничены Н*. На самом деле эта оценка является грубой. Пусть Б* - наибольшая степень вершины минимального остовного дерева для точек из К*. В разделе 2.1 доказано, что =8, Б*=6, 0*=12, Б* = 3*-1.

Метрики Lí и отличаются от других метрик Мшнсовского 1р, р> 1 тем, что единичные сферы в пространствах Ш* и являются многогранниками. Рассмотрим регион Я с началом в начале координат. Если пересечение региона Я с началом в начале координат и единичной сферы лежит целиком на одной из граней, то

Н ¿еШ* такое, что V уеК сКО,х)=<5Су-х) ( 2 )

Минимальное число узких регионов, удовлетряваих свойству (2) и покрывающих к-мерное пространство с метрикой ¿.р обозначим . Для региона, обладавшего свойством (2) получен алгоритм нахождения региональных соседей, требуввдий ОСп1одк"' а) времени и ОСМтО памяти. Алгоритм описан в разделе 2.8. Следующая теорема ."вляется клпчевой как для построения узких , регионов, так и проверки "узости" регионов.

Теорема 2.3. Пусть базис В=(Ь4> пространства с метрикой содержит векторы единичной длины. Для того, чтобы замкнутый ( полуоткрытый ) регион К для базиса В удовлетворял свойству (1) необходимо и достаточно, чтобы расстояния сКЬ'.Ы} для всех 1*/ были меньше ( не превосходили 3 1.

В разделах 2.2 - 2.5 построены узкие регионы для М-мер-ного пространства К* с Манхзттеновой метрикой.' При этом используется Теорема 2.3, которая позволяет свести построение узких регионов в пространстве к задаче триангуляции СМ-1Э-мерного куба. Для решения задачи триангуляции многомерного куба предложен жадный метод. Основная идея жадного метода триангуляции состоит в последовательном "вырезании" симплексов из куба, и при нахокдении очередного симплекса необходимо выбирать симплекс наибольшего объема. Жадный метод позволяет сократить число регионов можно с 2кМ! С обычная триангуляция куба 3 почти вдвое. Рассмотрим числовую последовательность ц , к-2,3,..., заданнуо с помощью рекурентного соотношения 1~1)+2 для к=3,4,. .. и иг=2, Число является, верх-

*ей оценкой числа Л-симплексов, сос*авляютих А-мериыЯ куб со зтороной 1 в силу теоремы.

Теорема 2.8. М-мерный куб К=(х|х4еСО, 11 для 1=1,2, ложно представить в виде объединения ^-симплексов, вершинами которых являются вершины куба <х|х е{0,1> для £■1,2.....,*>.

Следствие 2.1. теоремы 2.6 утверждает, что число узких мгионов соответствующих симплексам теоремы 2.6 равно .

В разделе 2.5 получена нижняя оценка числа узких регионов для пространства Нижняя оценка превышает все экспоненциальные оценки ПСск), с>0. Доказана

км

Теорема 2.7. N£>0(фкк * ).

На рис. 2 приведено сравнение верхних и нижних оценок цля числа узких регионов пространств размерности к£6.

к 3 4 5 6

Нижняя оценка 19 192 1100 6827

Верхняя оценка 48 320 2880 33408

Рис.2 Сравнение верхних и нижних оценок В разделе 2.6 дала конструкция узких регионов для прост-

ок

ранства Число построенных регионов равно 2кСк"' =0(—). Теорема 2.8. =£?С~О-

В разделе 2.7 приведены конструкции узких регионов для пространства 3£к£в, которые сокращают число регионов, полученных в разделе 2.6. Доказаны теоремы. Теорема 2.9. N^2*-4*32. Теорема 2.10. N'<2*-12=192.

Для построения узких регионов пространств размерности и й=6 используется

Теорема 2.11. Пусть /4с(ае$? ¡а >0, £ а =1} - семейство.

* л *

векторов и регионы ЯСВСаЗ.О) для всех аеЛ покрывают ортогональный регион ixJxt>0>. Тогда для любого те{1,2.....кУ полуоткрытые регионы R(B(a),i?i,0) для всех . ае4 покрывают полуоткрытый регион_<х|хт>0, х( >0 для i*m>.

Теорема 2.12. №<2В*55=830.

Для 6-мерного пространства следующая Теорема сокращает 2е'252-16128 регионов из Теоремы 2.8 до 8576 регионов.

Теорема 2.13. Г<2®-134=П76. На рис. 3 дано сравнение оценок числа "зких регионов, полученных в разделах 2.6 и 2.7 для размерности к£6.

k 3 ■ 4 S б

я 48 320 2240 18128

м» 32 192 880 8376

Рис.3 *) - регионы раздела 2.6, **) - регионы раздела 2.7. В разделе ¿.8 построен алгоритм сложности ОШод*."'- а) для задачи региональных соседей. Доказана

Теорема 2.14. Алгоритм Ш находит региональных соседей, за время 0(п1 одк"'Ю и использует ОСМп) объем памяти. В разделе 2.9 доказаны теоремы

Теорема 2.15 Пусть / - монотонно-возрастающая функция и Х^О для 1=1,2.....к. Минимальное остовное дерево на п вершинах в &22 можно построить за время 0С8кп(1одп)к"а1од1одп) • ( 0(2к&! п(1одп)к"г1од1ода) ), еоли веса •. ребер задаются

с!Си,«)=/{£ X |и -и р С йСи.у)* ¡(.тах(\ ).

• Теорема 2.10. Приближенное минимальное остовное дерево для п вершин в К*, к>2 с метрикой р>1 мояно построить за время сСсЗпС1одтг)1с"г1од1одп, где £>0 - погрешность врибликенйя В разделе 2.9 кроме задач нахождения минимального остовного дерева и региональных соседей исследуются следующие задачи :

(ближайший иностранный сосед) - Пусть У ,У .... -непересекаЕщиеся множества вершин, иК^К и |И|=п. Для всех У и каждой вершины найти вершину ие^ такую, что

d Си.иЭчгип d Cv,w)|weV\K, . AFP ?всв отдаленные точки)- Пусть У - мнояество п вершин. Для

каадой vzV найти ueV, что dpCv,u)=mtx dpCv,w) \гкУ . FP - Пусть V - мнояество п -вершин. Найти v,ueV такие, что dpCu,M)=max dp(x,y){х.уеК . ' ' '

Доказаны следующие теоремы

Теорема 2.17. Для задач NFN.AFP.FP в с (метрикой

L( С Lw ) существует алгоритм слозяости OCnCloga)*"8 l'ogloga).

Творзмв 2.10. Приближенное решение задач NFN, AFP.FP в

O^.teS , с метрикой i.p,рЯ модно найти за время

cCfi)nClogn)lt""loglogn, где с>0 - погрешность приближения.

Раздел 3 посвящен построению остовных деревьев минимального диамзтра. Трамвая задача построения остовного дерева минимального диаметра формулируется следующим образом. Дан взвешенный неориентированный граф G=CV,E). Найти остовное дерево Т для графа G, диаметр которого минимален. Определим диаметр взвешенного связного графа. Для каздой пары вершин и и v найдем минимальный С и, и) путь (u7v) С путь, у которого суша весов ребер минимальна ). Наибольший С по сумме весов ребер ) путь среди всех пар вершин называется диаметром графа. Гэрн и Дгонсон'1 доказали HP-трудность этой задачи.

Рассмотрим геоштрическую задачу построения остовного дерева-минимального диааетра. С каздой вераяной графа мы свя-кем некоторую точку я.з пространства Множество точек обозначим S. Граф - полный, т.е. каздая пара .вершин соединена ребром. Вес ребра, связывающего Две вершины, равен расстоянию мазду соответствующими точками в некоторой м&трике Lp.

Хо, Ли, Чанг иВонг®' показали, что остовное дерево минимального диаметра для южно построить за время ОСп3).

В разделе 3.1 доказано, что остовное дерево минимального

1 'rspn M., ifeoHcoH ft., BtjWHCiiiTe'BKKe ?^aiaHHU ;t TpyflHopeiaaef&te

aaaami // M , 1982.

2,Ko J., Lee D.T. , Chang C.-H., Wong C.K., Bounded-diameter

minimum spanning tree and related problems // Proc. 5-th Symposium on Computational Geometry // 1S89, P. 276-282. .

диаметра для плоскости о метрикой it шш 1и можно построить аа время OCn'logiü с использованием памяти ОСп). Алгоритм состоит нз двух шгов,4 На первом ваге рассматривается монопольные остовные деревья. Монопольное остовное дерево для любой точки и H3 >S содержит ребра С и, и) для всех ueS\<u>. Для подсчета диаметров монопольных деревьев применяется алгоритм нахождения региональных соседей из раздела 2.8.

На втором шаге рассматриваются днпольные остовные Царевы. Дипольное остовное дерево строится для любой пары точек и и v из S. При этом любая точка w из S отличная от V и и связывается с о»?ой из точек и или и, расстояние до которой меньше, чем до другой. Назовем вершины и и v полюсами '"дипольного остовного дерева.

Теорема 3.1. Остовное дерево минимального диаметра для п точек на плоскости с метрикой Lffl С или Lt ) можно построить за время OCn'logn) с использованием памяти ОСп).

■ Несмотря на то, что для плоскости найдены оптимальные алгоритмы построения минимального остовного дерева, в "ите-ратуре рассматривает частные случаи расположения точек на плоскости. Для некоторых частных случаев удается найти аффективные алгоритмы, требующие времени oCnloga). В частности, для случая, когда точхи расположены в вершинах унимодального многоугольника разработан'' линейный ОСп) алгоритм построения минимального остовного дерева. Поэтому модальность является характеристикой многоугольника, влияющей на сложность алгоритмов. В разделе 4 рассматривается задача вычисления модальности многоугольника.

Рассмотрим многоугольник Р содержащий п вершин. ,... ,ип> - множество вершин многоугольника. Многоугольник Р называется простым, если несмежные стороны не пересекаются. Мы не будем рассматривать частный случай nSZ. Пронумеруем вершины и ребра числами 0,1,...,п-1 как на рис. 4. Для удобства мы будем считать, что обозначение вершины и стороны является ее номером, номера вершин и сторон будем счи-

"Olariu S. <t simple linear-time algorithm for computing the RN3 and HST of unimdal polygons. // Inform. Proc. Letters. 1989. Vol. 31. P. 243-247.

тать по модули п.

Рис. 4. Нумерация верами и сторон многоугольника. Расстояние между двумя вершинами и и и в Евклидовой метрике обозначим d(.v,u). Рассмотрим две различные вершины и и и многоугольника Р. Вершина и является экстремальной вершиной для вершины v, если dCv,u-l)<d(v,u)>d(v,u+l) или dCv,u-lD>dCv,uXdCv,u+l). Упорядоченную пару вершин Си,Ю назовем экстремальной парой, если и - экстремальная вершина для вершина v. Экстремальностью вершины и назовем число вершин и, для которых и является экстремальной вершиной. В случае когда расстояния от нескольких последовательных вершин до некоторой вериины V равны мы определим экстремальное вершинное множество. Последовательность вершин iMu, ц+1,... ш> называется экстремальным вершинным множеством для вершины и, если выполнены следуодяе- два условия : аЭ dCv,u)=dCw,u+l)s.., =dCu,tt>

ЬЭ d(\J,u-13<dCD,u)>dCu,\i+i) или dCu,u~l)>ciCu,uXd(ti,w+13. Экстремумом вершины v является экстремальная вершина и для и или экстремальное вершинное множество U для и. Модальность вершины определяется как число ее экстремумов. Общее число экстремумов дает модальность многоугольника.' Многоугольник Р называется унимодальным, если модальность любой его вершины ie превосходит 1.

Агарвал и Мелвилл1' получали алгоритм сложности Otn+rrD да нахождения модальности выпуклого многоугольника, где а -1йсло вершин многоугольника и га - значение модальности много-

'Aggarwal А., Melville R. С. Fasi computation of the modality of polygons. // Journal of Algorithms. 1986. Vol. 7. Nr. 3. P. 269-381. .

угольника. Также они предложили алгоритм сложности 0(тй для распознавания унимодальности ¿выпуклого многоугольника. В 1' приведён пример выпуклого многоугольника с произвольным числом вершин, модальность которого оценивается ПСа2). Следовательно, алгоритм Агарвала-Мелвилла определяет модальность выпуклого многоугольника в худшем случае аа время СХп*).

В разделе 4.2 показано, что модальность выпуклого многоугольника можно вычислить за время ОСal ода). В разделе 4:5 доказано, -что алгоритм является оптимальным, т.е. любой алгоритм вычисляет модальность выпуклого многоугольника в худшем случае за время Q^loga). Если модальность ограничена ia=oCaloga), то этот алгоритм будет уступать алгоритму »Агарвала-Мелвилла. Поэтому мы дадим второй алгоритм с временной оценкой öCn+minCm.nlogiO). Для ' вычисления модальностей вершин выпуклого многоугольника мы представхш алгоритмы с такими же временными оценками. Кроме этого ш покажем как определить модальность простого многоугольника за время ОСп*'41 loga). Для определения модальностей всех вершив простого многоугольника мы дадим алгоритм сложности ОС а1 """3. Сравнение временных оценок приведено на рис S.

Для случая простого многоугольника Агарвал и Мелвнлл получили алгоритм сложности ОСа'"ввв) определения модальности многоугольника и алгоритм сложности 0(п' • *ав+пй определения модальностей всех вершин. F разделе 4.3 показано, что модальность простого многоугольника можно найти за ОС а' "*') шагов' и модальности всех вершин простого многоугольника - за ОСи1--""} шагов/

В основе алгоритма Агарвала-Мелвйлла для вычисления модальности простого многоугольника лежит задача запроса клина С wedge 'query ). Клин задается, с помощью двух пересекающихся прямых. Клином называется часть плоскости, образованная противоположными углами. Две пересекающиеся прямые определяют два клина и любая точка, не лежащая ни на одной прямой, принадлежит одному из клиньев. ЗадачФ к л и -

"Avis D., Toussaint G. Т., Bhattacharya В. К. On the mltimodality of distance ta a convex polygons. // Comput. Math. Appl. 1982. Vol. 8. Nr. 2. P. 153-106.

нового запроса формулируется следугшш обрчзом.

Задача Предыдущий результат . Ноьая ■ оценка

1. Модальность выпуклого ' ОСгг+Ю ОС alogrb

многоугольника OCn+minCm+nlogn))

2. Модальности вершин ПСп+пО OCnloqn)

выпуклого многоугольника ОС n+rai п( m+nl еда))

3. Модальность простого 0Сп'-в9В) £7Сп1'41 logn)

многоугольника

4. Модальности вершан 0Са' •ов"+п) Din' ■soa)

простого многоугольника

Рис. 5. •

Даны а точек на плоскости. Необходимо создать структуру данных для них тагсуа, чтобы могло било быстро отвечать на запроси следующего вида: Дан клин. Найти число аадашшх точек, прииадлэкацик клину.

Возьмем произвольную вершшг/ а простого многоугольника Р. Серединные перпендикуляры к сторонам смежным и обязательно юресекаптся и дапт два клина. Возьмем клин ¥, в котором тежит вершина и. Пусть клин W содержит к вершин шогоугояь-шка. Экстремальность вершины и равна к-1, т..к. любая вершина кроме и, дает экстремальную пару Cv,uJ. Эдельсбруинер я Велзл 11 рассмотрели задачу с запросом юлуплоскости С halfplanar query ) подобную задаче с клиновым ¡апросом. Они предложили структуру даиннх - сопрякенное дерево С conjugation tree ), которая позволяет давать ответ на ianpoc полуплоскости за время ОСп"), где а=1одСУг?+1)-1=Ю. 693.

'.0. Edelsbrunner H. , Welzl E. Half planar range search in linear space and 0Cn"'5OB) query time. // Inform. Proc Letters. 1986. .Vol. 23 . 289-293.

Сопряженное дпрзво аанкизэт обьеи_ псютк размера ОСп) н трз-бует ьрекени fXnlogn) для построения. На сгнои доле сопряког.-kos дерево nozaio использовать и дл.-: клинового запроса с тем to вроыен&м ответа ОСnR).

Коул и Ял1' -лредлоиита другоД подход для задачи клинового 'запроса, ibc структура данных позволяет найтн ответ на клкновый запрос оа время Oílognloglogn). К сожалению использовать эту структуру данных напрямую нельзя, т.к. ока требует памяти ОСп*) и время ее построения будет доминировать. Кобиннроваиие сопряженного дерева is структуры данных Коула н Йпа позволит доказать следующую теорему.

Teopsító 4.4. }{одальность простого многоугольника ыогко определить за время OCn*"blogn) с использованием памяти ОСаг*ь1одгО, где 2-b=2-log^bVy * 1.41.

Теорема 4.5. Модальности всех вершин простого многоугольника моено найти за время ОСпс) с использованной памяти ОСп), где c=log(vS+l) * 1.693.

Б разделе 4.8 доказано, что задача вычисления модальности выпуклого многоугольника имеет ннснсю временную оценку QCnlogrO. Для доказательства шшгах оценок многих задач вычислительной. геометрии используют результат Бон-Сра sl.

Пусть xi,xi,...,x - параметры задачи распознавания, какдый индивидуальный экземпляр которой ыогет считаться точкой в п-ыерном евклидовом пространстве Е". Задача распознавания определяет множество точек VsE", т.е. она дает отвэт

Дк тогда и только тогда, когда Cxt.....xn)tYJ. W - множество

истинности. Пусть обозначает число разделимых связных компонент W. Оказывается, что íKlog#VO - ниеняя временная оценха дшг любого алгоритма, реализованного в виде алгебраического дереьа'решений.

Теорема. С Бен-Op J Пусть М - множество в декартовом пространстве Ел, а Т - дереЕо решений фиксированного порядка

1 Cole R., Yap С. К. Gec.t¿4ric retrieval problem.' // Ргос.

24th Annual Synip.on Found, of Сотр. Sci.. 1S33. P. 112-121. a,Beri-0r K. Inner bounds for algebraic computation trees. // Proc. 15th ACM Annual Symp. on Theory on Conspui.. 1983. P. 80-86

d С. d>2 ), которое решает задачу о принадлежности W. Еспй h -высота Т, a ¿W - число связшк коотонент W, то h = íXlogA/-ri). .

ЙнпуклыЯ многоугольник задается с пс мощьО координат вершин (xt,ytЭти 2п чисел являются входом задачи определения модальности многоугольника. Каждому входу поставим в соответствие точку (х ,у ,х ,у ,... ,х ,у )оЕгп. Не лсбой

' о Jo ■ i ,Ji n-i -'n-i Г

точка из Ея" соответствует выпуклый употоугопън'лк. Рассмотрим задачу распознавания.

Дана точка реЕзп. Верно ли, что точки (pt ,ра), Срз,рА), ... ,Сргп_) определ.тат выпуклый многоугольник с обходом aepmm в направлении по часовой стрелке ?

Показано, что . эту задачу »оига выполнять за линейное время 0Сп). Рассмотрят другуа задачу распознавания.

Дана точка р;Еап. Впрно ли, что точки Cp¡, р„), С ps, ), ..., С Ргп_. т Ргг,) определяет выпуклый многоугольник с обходом гсрзшн в направлен:«! по часовой стрелке ¡i ого модальность равна ?

Есля эта задача требует времени ÍKnlogiO, то :i задача определения модальности выпуклого многоугольника имеет вре-меннуа оценку снизу fiCnlogn). Для второй задачи распознавания доказана

Теорема 4.0. Число связных кскгаснеят з ¡.шозествэ истинности для второй задачи распознавания выпуклого гс. -модального шгогоуголышка с п верэтпа'.п! оцсниваатся снизу rfk ^, где

, h-L-f-J-

Таким образом в силу теоремы Бен-Ора.и теоремы 4.3 ПСп1ода) является нижней временной оценкой задачи определения

модальности выпуклого многоугольника.

59

Основные результаты диссертации опубликованы в работах :

1.Беспамятных С. Н. Отимальный алгоритм построения минимального связывавшего дерева в полном плоской графа расстояний // Исследования по системному анализу и приложениям. / 1989. Урал. ун-т. Свердловск, С. 10-14.

2. Беспамятных J.Н. Построение минимальных сстовннх деревьев в fc-мерном пространстве с L метрика'-«! // Урал, ун-т..

•Свердловск, j 1990. Деп. ВИНИТИ. 22.03.50. V, 1530-390.

3. Беспамятный G.H. Построена ишшиапьник остовкшс деревьев в Урал, ун-т, Свердловск, 1S30, 8ç, Вназв,-Деп. ВИНИТИ, 03. И. 90, Jï 5626-В90.

4. Беспамятных С. Н. Эф^ктивныэ алгоритмы вычисления модальности многоугольников. Урал, ун-т, Екатеринбург, 1991, 2S с, 10 иазв, Деп. ВИНИТИ. 13.0S.91 К 2491-В91.

5. Яковлев H. Н. , Асанов М. 0., Баранский В. А. , Беспаиятных С. И. , ' Крутова Л. И.', Петров A. Н. , Харкн Б.Н. , Шамгунов Н. К. Развитие канального подхода в конструировании МЭА. Свердловск , 1987.