Вікіпедія

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

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

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

Опис ред.

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

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

Розв'язок за лінійний час ред.

Як показав Німрод Меґіддо[en][4], найменше обмежувальне коло можна знайти за лінійний час, і це ж істинне для найменшої обмежувальної сфери в евклідових просторах вищих розмірностей.

Емо Вельцль[en][5] запропонував простий рандомізований алгоритм для задачі покриття колом, середній час роботи якого дорівнює  , заснований на алгоритмі лінійного програмування Раймунда Зейделя. Алгоритм є рекурсивним і як аргументи приймає дві множини точок S і Q. Алгоритм обчислює найменше коло, що обмежує об'єднання множин S і Q, де будь-яка точка множини Q є граничною точкою можливого обмежувального кола. Початкову задачу про найменше обмежувальне коло можна розв'язати, почавши з S, рівної повній множині точок, і з Q, рівної порожній множині. Коли алгоритм викликає себе рекурсивно, він збільшує множину Q, поки в неї не потраплять усі граничні точки.

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

Пізніше завдання про найменше коло включено в загальний клас задач LP-типу[en], які можна розв'язати алгоритмами, подібними до алгоритму Вельцля, заснованого на лінійному програмуванні. Як наслідок приналежності до цього класу, показано, що залежність сталого множника від розмірності в оцінці часу  , яка була факторіальною в методі Зейделя, можна звести до субекспоненціальної, але оцінка часу залишається лінійною за N[6].

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

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

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

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

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

Див. також ред.

Примітки ред.

  1. ↑ а б Elzinga, Hearn, 1972, с. 96–104.
  2. ↑ Sylvester, 1857, с. 79.
  3. ↑ Francis, McGinnis, White, 1992.
  4. ↑ Megiddo, 1983, с. 759–776.
  5. ↑ Welzl, 1991, с. 359–370.
  6. ↑ Matoušek, Sharir, Welzl, 1996, с. 498–516.
  7. ↑ Chakraborty, Chaudhuri, 1981, с. 164–166.
  8. ↑ Elzinga, Hearn, 1972, с. 379–394.
  9. ↑ Drezner, Shelah, 1987, с. 255–261.
  10. ↑ Hearn, Vijay, Nickel, 1995, с. 236–237.
  11. ↑ Jacobsen, 1981, с. 144–148.
  12. ↑ а б в Hearn, Vijay, 1982, с. 777–795.
  13. ↑ Elzinga, Hearn, Randolph, 1976, с. 321–336.
  14. ↑ Lawson, 1965, с. 415–417.
  15. ↑ Shamos, Hoey, 1975, с. 151–162.
  16. ↑ Megiddo, 1983, с. 498–504.
  17. ↑ Megiddo, Zemel, 1986, с. 358–368.

Література ред.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Задача_про_найменше_коло&oldid=36241463