Задача про найменше коло

Зада́ча про найме́нше ко́ло або зада́ча про мініма́льне покривне́ ко́ло — задача про відшукання найменшого кола, яке містить всі задані точки з множини на евклідовій площині. Відповідна задача в n-вимірному просторі, задача про найменшу обмежувальну сферу, знаходить найменшу гіперсферу, яка містить усі точки заданої множиниШаблон:Sfn. Задачу про найменше коло 1857 року першим поставив англійський математик Джеймс Джозеф СильвестрШаблон:Sfn.

Завдання про найменше коло на площині — це приклад задачі про розміщення об'єктів (задача про 1-центр), у якій розташування нової організації потрібно вибрати так, щоб обслужити задану множину клієнтів з мінімізацією максимальної відстані, яку має подолати клієнт, щоб дістатися до організаціїШаблон:Sfn. Як задачу про найменше коло на площині, так і задачу про найменшу обмежувальну гіперсферу у вищих розмірностях можна розв'язати за лінійний час.

Опис

Більшість геометричних підходів до задачі включають перегляд точок, що лежать на межі мінімального кола і ґрунтуються на таких простих фактах:

• Найменше покривне коло єдине.
• Найменше покривне коло множини S можна визначити максимум за трьома точками з S, які лежать на межі кола. Якщо воно визначається лише двома точками, то хорда, що з'єднує ці точки, є діаметром найменшого кола. Якщо коло визначається трьома точками, то трикутник не може бути тупокутним.

Розв'язок за лінійний час

Як показав Шаблон:НпШаблон:Sfn, найменше обмежувальне коло можна знайти за лінійний час, і це ж істинне для найменшої обмежувальної сфери в евклідових просторах вищих розмірностей.

Шаблон:НпШаблон:Sfn запропонував простий рандомізований алгоритм для задачі покриття колом, середній час роботи якого дорівнює $O(N)$, заснований на алгоритмі лінійного програмування Раймунда Зейделя. Алгоритм є рекурсивним і як аргументи приймає дві множини точок S і Q. Алгоритм обчислює найменше коло, що обмежує об'єднання множин S і Q, де будь-яка точка множини Q є граничною точкою можливого обмежувального кола. Початкову задачу про найменше обмежувальне коло можна розв'язати, почавши з S, рівної повній множині точок, і з Q, рівної порожній множині. Коли алгоритм викликає себе рекурсивно, він збільшує множину Q, поки в неї не потраплять усі граничні точки.

Алгоритм опрацьовує точки множини S у випадковому порядку, використовуючи множину P опрацьованих точок і мінімальне коло, що обмежує об'єднання P і Q. На кожному кроці алгоритм перевіряє, чи належить опрацьовувана точка r цьому колу. Якщо не належить, алгоритм замінює обмежувальне коло рекурсивним викликом алгоритму на множинах P і Q+r. Залежно від того, замінюється коло чи ні, r включається у множину P. Опрацювання кожної точки, таким чином, полягає в перевірці (за сталий час), чи належить точка колу, і можливому рекурсивному виклику алгоритму. Можна показати, що i-та опрацьовувана точка має ймовірність $O(1/i)$ рекурсивного виклику, а тому загальний час лінійний.

Пізніше завдання про найменше коло включено в загальний клас Шаблон:Не перекладено, які можна розв'язати алгоритмами, подібними до алгоритму Вельцля, заснованого на лінійному програмуванні. Як наслідок приналежності до цього класу, показано, що залежність сталого множника від розмірності в оцінці часу $O(N)$, яка була факторіальною в методі Зейделя, можна звести до субекспоненціальної, але оцінка часу залишається лінійною за NШаблон:Sfn.

Інші алгоритми

До результату Меґіддо, який показує, що задачу про найменше коло можна розв'язати за лінійний час, у літературі з'являлися складніші алгоритми. Наївний алгоритм розв'язує задачу за час O(n⁴) шляхом перевірки кіл, задаваних усіма парами і трійками точок.

• Алгоритм Христала і Пірса використовує стратегію локальної оптимізації. Алгоритм переглядає дві точки на межі обмежувального кола і послідовно зменшує коло, замінюючи пари обмежувальних точок, поки не буде знайдено оптимальне коло. Чакраборті і ЧаудгуріШаблон:Sfn запропонували для вибору підхожого початкового кола і пари граничних точок на колі метод з лінійним часом роботи. Кожен крок алгоритму включає як другу обмежувальну точки нову вершину опуклої оболонки, так що, якщо опукла оболонка має h вершин, цей метод може працювати за час O(nh).
• Елзинга і ГірнШаблон:Sfn описали алгоритм, який розглядає обмежувальні сфери для підмножини точок. На кожному кроці точка, що лежить поза сферою, використовується для пошуку більшої сфери, яка включає нову підмножину точок, до якої входить ця точка. Хоча найгірший випадок роботи алгоритму оцінюється як O(h³n), автори стверджують, що в їхніх експериментах алгоритм працював за лінійний час. Складність методу проаналізували Дрезнер і ШелахШаблон:Sfn. У статті Гірна, Віджея і Нікеля можна знайти коди методу на Фортрані і CШаблон:Sfn.
• Задачу про найменшу сферу можна сформулювати як задачу квадратичного програмуванняШаблон:Sfn, визначену як систему лінійних обмежень з опуклою квадратичною цільовою функцією. Таким чином, будь-який алгоритм можливих напрямків може дати розв'язок задачіШаблон:Sfn. Гірн та ВіджейШаблон:Sfn довели, що підхід на основі методу можливих напрямків, обраний Якобсеном, еквівалентний алгоритму Христала — Пірса.
• Двоїсту задачу задачі квадратичного програмування можна сформулювати явноШаблон:Sfn. Алгоритм ЛовсонаШаблон:Sfn можна описати як алгоритм одночасного розв'язання прямої і двоїстої задачШаблон:Sfn.
• Шеймос і ГойШаблон:Sfn запропонували алгоритм з часом розв'язування O(n log n), заснований на спостереженні, що центр найменшого обмежувального кола має бути вершиною найвіддаленішої точки в діаграмі Вороного вхідної множини точок.

Зважені варіанти задачі

Зважена версія задачі про найменше покривне коло має вхідними даними точки евклідового простору, кожній з яких призначено вагу. Метою задачі є пошук однієї точки, що мінімізує найбільшу зважену відстань до будь-якої точки. Початкову задачу покриття колом можна розглядати як задачу з однаковими вагами. Як і у випадку задачі без ваг, зважену задачу можна розв'язати за лінійний час у будь-якому просторі обмеженої розмірності, якщо використати підхід, заснований на алгоритмі лінійного програмування обмеженої розмірності, хоча в літературі постійно зустрічаються повільніші алгоритмиШаблон:SfnШаблон:SfnШаблон:Sfn.

Див. також

• Обмежувальна сфера
• Описане коло
• Шаблон:Не перекладено

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Bernd Gärtner's smallest enclosing ball code Шаблон:Webarchive
• CGAL Шаблон:Webarchive — пакунок Min_sphere_of_spheres у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)
• Miniball Шаблон:Webarchive — реалізація з відкритими сирцями алгоритму для задачі про найменшу обмежувальну кулю для низьких і помірно високих розмірностей