Попередня Змiст Наступна

ГЛАВА 1. ВСТУП

Єгипетська і грецька геометрії являються шедевром прикладної математики, фундаментом математичної думки. Одним із основоположників античної геометрії по праву вважається Евклід. Головним вкладом його в геометрію, викладеному в "Началах," є: аксіоматичний метод доведення - твердження, які приймаються без доведення; евклідова побудова - схема, яка складається із алгоритму та його доведення.
  Евклідова побудова визначає набір допустимих інструментів (лінійка, циркуль) та множину допустимих операцій (примітивів), які можна виконати з їх допомогою. Важливим є питання повноти системи евклідових примітивів при умові скінченності числа операцій. Архімед, у свій час, запропонував (коректну) конструкцію для задачі трисекції кута у 60° додавши нові примітиви. У деяких випадках вивчається обмежений набір примітивів. Доведення неповноти системи евклідових примітивів прийшло з розвитком алгебри.
  Вплив геометрії Евкліда був настільки сильним, що інших нових формулювань геометрії не було запропоновано аж до Декарта, який, ввівши систему координат, зумів виразити геометричні задачі алгебраїчно і перейти до вивчення плоских кривих вищих порядків і ньютонівського аналізу. Декартові координати дозволили значно підвищити обчислювальні можливості геометричних задач. З'явилась можливість описувати геометричні об'єкти за допомогою алгебраїчних рівнянь, що розширило можливості їх дослідження і поставило нові питання обчислювальності. Розв'язанням цих питань серйозно займались такі геніальні математики, як Гаус та Абель. У своїй докторський дисертації Гаус показав, що у будь-якого алгебраїчного рівняння існує принаймні один корінь (основна теорема алгебри). Абель у 1828 році взявся за розв'язання питання про те, чи можна знайти корінь будь-якого алгебраїчного рівняння, скориставшись тільки арифметичними операціями і здобуттям коренів n-ої степені, і довів, що цього зробити не можна.
  Задача визначення кількісної міри складності була сформульована лише у 1902 році Лемуаном, який систематизував евклідові примітиви таким чином: поставити одну ніжку циркуля в дану точку, поставити одну ніжку циркуля на дану пряму, провести коло, сумістити ребро лінійки з даною точкою, провести лінію. Загальна кількість таких операцій називається простотою побудови. Це визначення близьке до часової складності алгоритму, хоча у ньому відсутній функціональний зв'язок між розміром вхідних даних (числом заданих точок і ліній) для геометричної побудови і її простоти. Лемуану вдалось покращити евклідовий розв'язок задачі про круги Аполонія з 508 кроків Евкліда до 200 кроків. Але Лемуан не звернув увагу на нижні оцінки складності алгоритму. Гілберт на обмеженій моделі розглядав такі побудови, які можна виконати за допомогою односторонньої лінійки і шкали. Але не усі евклідові побудови можна виконати за допомогою цього набору інструментів. Розглядаючи координати побудованих точок як деяку функцію  f  від заданих точок, Гілберт сформулював необхідну та достатню умови обчислювальності  f  з використанням рівно n операцій здобуття квадратного кореня. У 1972 році Джордж Мор показав, що будь-яку побудову, яка здійснюється за допомогою циркуля і лінійки, можна виконати лише циркулем у випадку, коли шукані об'єкти визначаються точками. Тобто висувається ідея моделювання, за допомогою якого будь-яку операцію, у якій бере участь лінійка, можна замінити скінченим числом операцій циркуля.
  Лемуан й інші математики вивчали не лише часову складність евклідових побудов, але й підіймали питання про об'єм простору, необхідний для цих побудов.
  Передісторія назви "Обчислювальна геометрія". Вперше офіційно на російській мові ця назва з'явилася із виходом у видавництві "МИР" 1982 року монографії Фокса А. і М. Пратта "Вычислительная геометрия. Применение в проектировании и производстве ", де йшла мова про задачі геометричного моделювання. А через шість років по тому у тому ж видавництві російською мовою вийшла монографія М. Шеймоса та Ф. Препарата з тією ж назвою, але в якій іде мова про аналіз оцінок складності та побудови ефективних комбінаторних алгоритмів для розв'язання геометричних задач.
  Парадокс пояснюється просто: як один, так і інший напрями народилися недавно і їх становлення та інтенсивний розвиток протікали одночасно, обидва напрямки мають глибокі геометричні корені і безпосередній зв'язок із ЕОМ. На сьогоднішній день за першим напрямком закріпилась назва - "Геометричне моделювання", за іншим лишилась назва "Обчислювальна геометрія".
Означення 1.1 Обчислювальна геометрія - це наука, предметом дослідження якої є аналіз та побудова ефективних алгоритмів розв'язання геометричних задач, оцінки їх складності в рамках теорії алгоритмів.
  1. Застосування.

    2. Обчислювальна геометрія має широке коло застосувань. Це робототехніка, проектування СВІС , бази даних, дослідження операцій , теорія керування, комп'ютерна графіка та ін.
  2. Основні класи задач:

    3. У відповідності з природою геометричних об'єктів можна вділити 5 основних класів задач:опуклість, перетин, геометричний пошук, близькість, оптимізація. Окрім цього, по способу обробки виділяють три типи задач:
    1) пошук підмножини. Задається набір об'єктів, необхідно знайти підмножину, яка задовольняє певній умові. Наприклад: пошук найближчої пари. Характерним для таких задач є те, що не треба створювати нових об'єктів.
    2) обчислення. Необхідно обчислити деякий геометричний параметр на заданій множині об'єктів. Наприклад: визначити максимальну (мінімальну) відстань між точками. Тут вимагається наявність математичних можливостей реалізації алгоритму.
    3) розпізнавання. Задача розпізнавання пов'язана з двома попередніми типами. Якщо в Задачі А обчислення треба знайти величину параметра а, то в зв'язаній з нею задачі розпізнавання треба дати відповідь ДА/НІ на питання: " Вірно, що а>а" ?" . опуклість, перетин, геометричний пошук, близькість, оптимізація.
  3. Приклади задач які розв'язує ОГ.

  4. Напрямки обробки зображувальної інформації:

    5. розпізнавання образів, обробка зображень, комп'ютерна графіка.
    1) основна задача розпізнавання образів полягає у перетворені уже існуючого зображення на формальну зрозумілу мову символів. Розпізнавання образів є сукупність методів, які дозволяють отримати опис зображення поданого на вхід, або віднести задане зображення до якогось класу. (сортування пошти, медична діагностика і томографія)
    2) обробка зображень розглядає задачі, в яких вхідні і вихідні дані є зображеннями.( передача зображень разом із погашенням шумів і стискання даних, перехід від одного типу зображень(напівтонового) до іншого ( каркасного), контрастування різних знімків, також синтез існуючих зображень у нові).
    3) комп'ютерна графіка створює зображення у випадку, коли початковою є інформація не зображувальної природи. Наприклад, візуалізація експериментальних даних у вигляді графіків, гістограм чи діаграм, вивід інформації на екран у комп'ютерних іграх, синтез сцен для тренажерів.
  5. Напрями комп'ютерної графіки:

    6. 1) ілюстративний, який можна розуміти починаючи з пояснень (візуалізації) результатів експерименту і закінчуючи створенням рекламних роликів.
    2) саморозвиваючий - КГ повинна обслуговувати свої потреби, розширюючи свої можливості та удосконалюючи їх.
    3) дослідницький, в якому інструментарій КГ починає грати роль, яка подібна тій , яку у свій час зіграв мікроскоп.


Попередня Змiст Наступна