Побудова опуклої оболонки. Методи

6. Найближча пара, метод «Розділяй та пануй»

Примітка1: часову оцінку складності сортування списку точок по координаті х віднесемо до попередньої обробки вхідної множини, в найгіршому випадку сортування буде потребувати O(), а в кращому O(Nlog2N). Сортування множини точок по координаті у можно виконувати за O() прямо під час кроку злиття двох вже відсортованих по у множин.

Примітка2: на етапі злиття, маючи відсортовані по y точки, ми розглядаємо відстань тільки між тими точками, між якими різниця ординат менше нашої мінімальної дистанції (а не відстань між всіма точками першої і другої множин).

Примітка3 (для тих, кто сумнівається, що крок 6 виконується за лінійний час):

Примітка4 (сама очевидність): щоб показати, що часова оцінка складності дійсно дорівнює O(Nlog2N) треба показати, що часова оцінка на кроці злиття дорівнює O(), а враховуючи Примітку2 і Примітку3 бачимо, що це так і є.