ГЛАВА 2
АЛГОРИТМИ ПОБУДОВИ ЕЛІПСА МІНІМАЛЬНОЇ
ПЛОЩІ ТА ТРИКУТНИКА НАЙБІЛЬШОЇ ПЛОЩІ
Як легко зрозуміти при початку роботи над деякою проблемою, пов'язаною із побудовою алгоритму її знаходження, то перше, що повинно цікавити дослідника, так це взагалі принципова можливість коректного розв'язання проблеми. Нехай нема ефективності, але потрібна збіжність алгоритму до потрібної величини, тобто слушність обраного методу для розв'язання поставленої проблеми. Це ми називаємо принциповий алгоритм знаходження відповідного об'єкту.
Якщо на це принципове запитання одержана позитивна відповідь (інакше спочатку треба шукати саме її), то можна приступати до розробки більш менш ефективних алгоритмів. При цьому виникає декілька напрямів його дослідження. Перелічимо їх в довільному порядку. Чи існує точний розв'язок задачі; наскільки витрати наближеного розв'язку менші в порівнянні з точним алгоритмом; що вважати за точність наближення; як впливає накопичення похибки на одержаний результат; оцінка складності роботи алгоритму; практична поведінка розробленого алгоритму на тестових прикладах; порівняння між собою існуючих алгоритмів на різних тестах, особливо для граничних (майже вироджених) випадків; та деякі інші.
Саме цими питаннями переймався автор, коли починав дослідження проблеми побудови ЕМП. Вивчення геометричних властивостей ЕМП дало змогу відповісти на принципове питання можливості його побудови, що виключав повний перебір множини усіх підмножин заданого набору точок, а лише звів його до перегляду доволі обмеженої кількості підмножин. Далі були одержані відповіді на усі інші принципові питання, за виключенням хіба що точної оцінки складності роботи алгоритмів. Але практична їх реалізація, перевірка на тестових прикладах, порівняння з існуючими алгоритмами, підтвердили їх ефективність. Показана стійкість алгоритмів по відношенню до накопичення похибки обчислень, що є чудовою характеристикою для подібних проблем, які оперують великими масивами даних.
Були розроблені два типи наближених алгоритмів та проведена оцінка точності одержаного наближення, один з яких безпосередньо спирається на метод побудови ТНП.
Для ТНП було зроблене повністю аналогічне дослідження. Крім того показано, що алгоритм працює за лінійний час, тестування показало ефективність обох існуючих алгоритмів, які в подальшому були певною мірою узагальнені на випадок тривимірного простору.
2.1. Принциповий алгоритм побудови еліпса мінімальної площі
Нагадаю, що має місце наступна теорема [172].
Теорема 2.1.1.ЕМП для довільного опуклого многокутника єдиний.
Теорема 2.1.2.Довести що:
а) якщо ЕМП для многокутника містить рівно чотири вершини M, то жоден з ЕМП, побудованих для всіх інших чотирикутників вигляду , де не оточує повністю многокутник M.
б) якщо ЕМП для многокутника містить рівно п'ять вершин M, то жоден з ЕМП, побудованих для інших п'ятикутників, де не містить всередині повністю многокутник M.
Доведення. Почнемо з першої частини, та проведемо його методом від супротивного. Нехай e - ЕМП для многокутника M, що проходить рівно через чотири вершини , , , многокутника M, а - ЕМП деякого іншого чотирикутника . Припустимо, що , тоді якщо , то це суперечить теоремі 1.6.1, тому . Але тоді не є ЕМП для чотирикутника , тому що і . Одержали протиріччя, що доводить лему.
Повністю аналогічно доводиться також друга частина теореми.
Перейдемо тепер до описання принципового алгоритму побудови ЕМП для довільного опуклого многокутника .
Алгоритм 2.1.1
(Принциповий алгоритм побудови ЕМП).
1-й крокРозглянемо всі трикутники вигляду , де , що утворені вершинами многокутника M, серед них знаходимо трикутник найбільшої площі. Для цього трикутника будуємо ЕМП ; якщо виконується включення , то шуканий ЕМП для всього многокутника M, і алгоритм побудови ЕМП завершується; якщо ж , то переходимо до наступного кроку.2-й крокРозглянемо всі чотирикутники вигляду , що утворюються вершинами многокутника M. Внаслідок зауваження 1.6.1 необхідно для кожного з них перевірити умову , де є ЕМП для відповідного чотирикутника (і серед усіх ЕМП розглядаємо лише ті, що містять усі чотири його вершини, бо інакше цей еліпс вже було б розглянуто на першому кроці алгоритму). Якщо ця умова виконується для одного з чотирикутників, то відповідний ЕМП буде ЕМП для всього многокутника M (дивись теорему 2.1.2), і алгоритм завершує роботу. Якщо ж включення не виконується для жодного з еліпсів , то переходимо до останнього кроку роботи алгоритму.3-й крокРозглянемо всі можливі п'ятикутники , , що утворюються вершинами многокутника M, і для кожного з них побудуємо відповідний ЕМП (знову ми розглядаємо лише ті ЕМП, що містять усі вершини відповідного п'ятикутника, а тому він будується дуже легко, бо він є описаним навколо заданого опуклого п'ятикутника, а тому він існує єдиний). Серед усіх таких ЕМП існує єдиний, що містить многокутник M. Цей ЕМП і є шуканим, і алгоритм завершує свою роботу.
Зрозуміло, що наведений алгоритм дає лише принципову відповідь про можливість побудови ЕМП, ні про яку оптимальність чи ефективність подібного алгоритму говорити поки що не слід. Але використовуючи більшість з одержаних геометричних властивостей далі ми запропонуємо вже оптимальні та ефективні алгоритми побудови еліпса мінімальної площі.
2.2. Алгоритми побудови трикутника максимальної площі
Спираючись на леми 1.4.1-1.4.2 можемо запропонувати такий алгоритм побудови базового трикутника , тобто трикутника найбільшої площі, що міститься всередині опуклого многокутника , у якого одна з вершин знаходиться в точці [156].
Алгоритм 2.2.1
(Алгоритм побудови ба