152
Minimal qavariq qobiq tushunchasi.
Tekislikda cheklangan A
nuqtalar to'plami berilgan bo'lsin. Bu to'plamning konvertlari o'zaro
kesishmalarsiz har qanday yopiq H chiziq bo'lib, A ning barcha nuqtalari
shu egri chiziq ichida yotadi. Agar H egri chiziq qavariq bo'lsa (masalan,
bu egri chiziqning har qanday urinish nuqtasi uni boshqa biron bir
nuqtada kesib o'tmasa), u holda tegishli qobiq ham qavariq deb ataladi.
Va nihoyat, minimal qavariq qobiq minimal uzunlikdagi (minimal
perimetr) qavariq qobiq deb ataladi. Barcha kiritilgan tushunchalar
quyidagi 55-rasmda keltirilgan.
A nuqtalar to'plamli minimal qavariq qobiqning asosiy xususiyati
shundaki, bu tanasi qavariq ko'pburchak bo'lib, uning uchlari A dagi bir
nechta nuqtadir, shuning uchun minimal qavariq qobiqni topish
muammosi oxir-oqibat A dan kerakli nuqtalarni tanlash va
tartiblashgacha kamayadi. Algoritm chiqishi ko'pburchak bo'lishi
kerakligi sababli tartiblash ya‘ni saralash zarur, ya'ni uchlar ketma-
ketligi boʻyicha. Uchlar tartibiga qo'shimcha ravishda shart qo'yamiz -
ko'pburchakning o'tish yo'nalishi musbat bo'lishi kerak (soat strelkasi
boʻyicha).
