Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Зада ча про найме нше ко ло або зада ча про мініма льне покривне ко ло задача про відшукання найменшого кола яке містить

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

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

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

image

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

Опис

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  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.

Література

  • J. Elzinga, D. W. Hearn. The minimum covering sphere problem // . — 1972. — Т. 19. — DOI:10.1287/mnsc.19.1.96.
  • J. J. Sylvester. A question in the geometry of situation // . — 1857. — Т. 1. — С. 79.
  • R. L. Francis, L. F. McGinnis, J. A. White. Facility Layout and Location: An Analytical Approach. — 2nd. — Englewood Cliffs, N.J. : Prentice–Hall, Inc, 1992.
  • Nimrod Megiddo. Linear-time algorithms for linear programming in R3 and related problems // . — 1983. — Т. 12, вип. 4. — С. 759–776. — DOI:10.1137/0212052.
  • Emo Welzl. New Results and New Trends in Computer Science / H. Maurer. — Springer-Verlag, 1991. — Т. 555. — С. 359–370. — (Lecture Notes in Computer Science) — DOI:10.1007/BFb0038202.
  • Jiří Matoušek, Micha Sharir, Emo Welzl. A subexponential bound for linear programming // . — 1996. — Т. 16. — С. 498–516. — DOI:10.1007/BF01940877. з джерела 12 серпня 2017. Процитовано 30 травня 2022.
  • R. K. Chakraborty, P. K. Chaudhuri. Note on geometrical solutions for some minimax location problems // . — 1981. — Т. 15. — DOI:10.1287/trsc.15.2.164.
  • J. Elzinga, D. W. Hearn. Geometrical solutions for some minimax location problems // . — 1972. — Т. 6. — С. 379–394. — DOI:10.1287/trsc.6.4.379.
  • Z. Drezner, S. Shelah. On the complexity of the Elzinga–Hearn algorithm for the 1-center problem // . — 1987. — Т. 12, вип. 2. — С. 255–261. — DOI:10.1287/moor.12.2.255.
  • D. W. Hearn, J. Vijay, S. Nickel. Codes of geometrical algorithms for the (weighted) minimum circle problem // European Journal of Operational Research. — 1995. — Т. 80. — DOI:10.1016/0377-2217(95)90075-6.
  • S. K. Jacobsen. An algorithm for the minimax Weber problem // European Journal of Operational Research. — 1981. — Т. 6. — DOI:10.1016/0377-2217(81)90200-9.
  • D. W. Hearn, J. Vijay. Efficient algorithms for the (weighted) minimum circle problem // . — 1982. — Т. 30, вип. 4. — DOI:10.1287/opre.30.4.777.
  • J. Elzinga, D. W. Hearn, W. D. Randolph. Minimax multifacility location with Euclidean distances // . — 1976. — Т. 10. — DOI:10.1287/trsc.10.4.321.
  • C. L. Lawson. The smallest covering cone or sphere // . — 1965. — Т. 7, вип. 3. — DOI:10.1137/1007084.
  • M. I. Shamos, D. Hoey. . — 1975. — DOI:10.1109/SFCS.1975.8.
  • N. Megiddo. The weighted Euclidean 1-center problem // . — 1983. — Т. 8. — DOI:10.1287/moor.8.4.498.
  • N. Megiddo, E. Zemel. An O(n log n) randomizing algorithm for the weighted Euclidean 1-center problem // Journal of Algorithms. — 1986. — Т. 7. — DOI:10.1016/0196-6774(86)90027-1.

Посилання

  • Bernd Gärtner's smallest enclosing ball code [ 31 серпня 2009 у Wayback Machine.]
  • CGAL [ 24 вересня 2013 у Wayback Machine.] — пакунок Min_sphere_of_spheres у Бібліотеці алгоритмів обчислювальної геометрії (Computational Geometry Algorithms Library, CGAL)
  • Miniball [ 30 травня 2022 у Wayback Machine.] — реалізація з відкритими сирцями алгоритму для задачі про найменшу обмежувальну кулю для низьких і помірно високих розмірностей

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zada cha pro najme nshe ko lo abo zada cha pro minima lne pokrivne ko lo zadacha pro vidshukannya najmenshogo kola yake mistit vsi zadani tochki z mnozhini na evklidovij ploshini Vidpovidna zadacha v n vimirnomu prostori zadacha pro najmenshu obmezhuvalnu sferu znahodit najmenshu gipersferu yaka mistit usi tochki zadanoyi mnozhini Zadachu pro najmenshe kolo 1857 roku pershim postaviv anglijskij matematik Dzhejms Dzhozef Silvestr Zavdannya pro najmenshe kolo na ploshini ce priklad zadachi pro rozmishennya ob yektiv zadacha pro 1 centr u yakij roztashuvannya novoyi organizaciyi potribno vibrati tak shob obsluzhiti zadanu mnozhinu kliyentiv z minimizaciyeyu maksimalnoyi vidstani yaku maye podolati kliyent shob distatisya do organizaciyi Yak zadachu pro najmenshe kolo na ploshini tak i zadachu pro najmenshu obmezhuvalnu gipersferu u vishih rozmirnostyah mozhna rozv yazati za linijnij chas OpisBilshist geometrichnih pidhodiv do zadachi vklyuchayut pereglyad tochok sho lezhat na mezhi minimalnogo kola i gruntuyutsya na takih prostih faktah Najmenshe pokrivne kolo yedine Najmenshe pokrivne kolo mnozhini S mozhna viznachiti maksimum za troma tochkami z S yaki lezhat na mezhi kola Yaksho vono viznachayetsya lishe dvoma tochkami to horda sho z yednuye ci tochki ye diametrom najmenshogo kola Yaksho kolo viznachayetsya troma tochkami to trikutnik ne mozhe buti tupokutnim Rozv yazok za linijnij chasYak pokazav en najmenshe obmezhuvalne kolo mozhna znajti za linijnij chas i ce zh istinne dlya najmenshoyi obmezhuvalnoyi sferi v evklidovih prostorah vishih rozmirnostej en zaproponuvav prostij randomizovanij algoritm dlya zadachi pokrittya kolom serednij chas roboti yakogo dorivnyuye O N displaystyle O N zasnovanij na algoritmi linijnogo programuvannya Rajmunda Zejdelya Algoritm ye rekursivnim i yak argumenti prijmaye dvi mnozhini tochok S i Q Algoritm obchislyuye najmenshe kolo sho obmezhuye ob yednannya mnozhin S i Q de bud yaka tochka mnozhini Q ye granichnoyu tochkoyu mozhlivogo obmezhuvalnogo kola Pochatkovu zadachu pro najmenshe obmezhuvalne kolo mozhna rozv yazati pochavshi z S rivnoyi povnij mnozhini tochok i z Q rivnoyi porozhnij mnozhini Koli algoritm viklikaye sebe rekursivno vin zbilshuye mnozhinu Q poki v neyi ne potraplyat usi granichni tochki Algoritm opracovuye tochki mnozhini S u vipadkovomu poryadku vikoristovuyuchi mnozhinu P opracovanih tochok i minimalne kolo sho obmezhuye ob yednannya P i Q Na kozhnomu kroci algoritm pereviryaye chi nalezhit opracovuvana tochka r comu kolu Yaksho ne nalezhit algoritm zaminyuye obmezhuvalne kolo rekursivnim viklikom algoritmu na mnozhinah P i Q r Zalezhno vid togo zaminyuyetsya kolo chi ni r vklyuchayetsya u mnozhinu P Opracyuvannya kozhnoyi tochki takim chinom polyagaye v perevirci za stalij chas chi nalezhit tochka kolu i mozhlivomu rekursivnomu vikliku algoritmu Mozhna pokazati sho i ta opracovuvana tochka maye jmovirnist O 1 i displaystyle O 1 i rekursivnogo vikliku a tomu zagalnij chas linijnij Piznishe zavdannya pro najmenshe kolo vklyucheno v zagalnij klas en yaki mozhna rozv yazati algoritmami podibnimi do algoritmu Velclya zasnovanogo na linijnomu programuvanni Yak naslidok prinalezhnosti do cogo klasu pokazano sho zalezhnist stalogo mnozhnika vid rozmirnosti v ocinci chasu O N displaystyle O N yaka bula faktorialnoyu v metodi Zejdelya mozhna zvesti do subeksponencialnoyi ale ocinka chasu zalishayetsya linijnoyu za N Inshi algoritmiDo rezultatu Megiddo yakij pokazuye sho zadachu pro najmenshe kolo mozhna rozv yazati za linijnij chas u literaturi z yavlyalisya skladnishi algoritmi Nayivnij algoritm rozv yazuye zadachu za chas O n4 shlyahom perevirki kil zadavanih usima parami i trijkami tochok Algoritm Hristala i Pirsa vikoristovuye strategiyu lokalnoyi optimizaciyi Algoritm pereglyadaye dvi tochki na mezhi obmezhuvalnogo kola i poslidovno zmenshuye kolo zaminyuyuchi pari obmezhuvalnih tochok poki ne bude znajdeno optimalne kolo Chakraborti i Chaudguri zaproponuvali dlya viboru pidhozhogo pochatkovogo kola i pari granichnih tochok na koli metod z linijnim chasom roboti Kozhen krok algoritmu vklyuchaye yak drugu obmezhuvalnu tochki novu vershinu opukloyi obolonki tak sho yaksho opukla obolonka maye h vershin cej metod mozhe pracyuvati za chas O nh Elzinga i Girn opisali algoritm yakij rozglyadaye obmezhuvalni sferi dlya pidmnozhini tochok Na kozhnomu kroci tochka sho lezhit poza sferoyu vikoristovuyetsya dlya poshuku bilshoyi sferi yaka vklyuchaye novu pidmnozhinu tochok do yakoyi vhodit cya tochka Hocha najgirshij vipadok roboti algoritmu ocinyuyetsya yak O h3n avtori stverdzhuyut sho v yihnih eksperimentah algoritm pracyuvav za linijnij chas Skladnist metodu proanalizuvali Drezner i Shelah U statti Girna Vidzheya i Nikelya mozhna znajti kodi metodu na Fortrani i C Zadachu pro najmenshu sferu mozhna sformulyuvati yak zadachu kvadratichnogo programuvannya viznachenu yak sistemu linijnih obmezhen z opukloyu kvadratichnoyu cilovoyu funkciyeyu Takim chinom bud yakij algoritm mozhlivih napryamkiv mozhe dati rozv yazok zadachi Girn ta Vidzhej doveli sho pidhid na osnovi metodu mozhlivih napryamkiv obranij Yakobsenom ekvivalentnij algoritmu Hristala Pirsa Dvoyistu zadachu zadachi kvadratichnogo programuvannya mozhna sformulyuvati yavno Algoritm Lovsona mozhna opisati yak algoritm odnochasnogo rozv yazannya pryamoyi i dvoyistoyi zadach Shejmos i Goj zaproponuvali algoritm z chasom rozv yazuvannya O n log n zasnovanij na sposterezhenni sho centr najmenshogo obmezhuvalnogo kola maye buti vershinoyu najviddalenishoyi tochki v diagrami Voronogo vhidnoyi mnozhini tochok Zvazheni varianti zadachiZvazhena versiya zadachi pro najmenshe pokrivne kolo maye vhidnimi danimi tochki evklidovogo prostoru kozhnij z yakih priznacheno vagu Metoyu zadachi ye poshuk odniyeyi tochki sho minimizuye najbilshu zvazhenu vidstan do bud yakoyi tochki Pochatkovu zadachu pokrittya kolom mozhna rozglyadati yak zadachu z odnakovimi vagami Yak i u vipadku zadachi bez vag zvazhenu zadachu mozhna rozv yazati za linijnij chas u bud yakomu prostori obmezhenoyi rozmirnosti yaksho vikoristati pidhid zasnovanij na algoritmi linijnogo programuvannya obmezhenoyi rozmirnosti hocha v literaturi postijno zustrichayutsya povilnishi algoritmi Div takozhObmezhuvalna sfera Opisane kolo en PrimitkiElzinga Hearn 1972 s 96 104 Sylvester 1857 s 79 Francis McGinnis White 1992 Megiddo 1983 s 759 776 Welzl 1991 s 359 370 Matousek Sharir Welzl 1996 s 498 516 Chakraborty Chaudhuri 1981 s 164 166 Elzinga Hearn 1972 s 379 394 Drezner Shelah 1987 s 255 261 Hearn Vijay Nickel 1995 s 236 237 Jacobsen 1981 s 144 148 Hearn Vijay 1982 s 777 795 Elzinga Hearn Randolph 1976 s 321 336 Lawson 1965 s 415 417 Shamos Hoey 1975 s 151 162 Megiddo 1983 s 498 504 Megiddo Zemel 1986 s 358 368 LiteraturaJ Elzinga D W Hearn The minimum covering sphere problem 1972 T 19 DOI 10 1287 mnsc 19 1 96 J J Sylvester A question in the geometry of situation 1857 T 1 S 79 R L Francis L F McGinnis J A White Facility Layout and Location An Analytical Approach 2nd Englewood Cliffs N J Prentice Hall Inc 1992 Nimrod Megiddo Linear time algorithms for linear programming in R3 and related problems 1983 T 12 vip 4 S 759 776 DOI 10 1137 0212052 Emo Welzl New Results and New Trends in Computer Science H Maurer Springer Verlag 1991 T 555 S 359 370 Lecture Notes in Computer Science DOI 10 1007 BFb0038202 Jiri Matousek Micha Sharir Emo Welzl A subexponential bound for linear programming 1996 T 16 S 498 516 DOI 10 1007 BF01940877 z dzherela 12 serpnya 2017 Procitovano 30 travnya 2022 R K Chakraborty P K Chaudhuri Note on geometrical solutions for some minimax location problems 1981 T 15 DOI 10 1287 trsc 15 2 164 J Elzinga D W Hearn Geometrical solutions for some minimax location problems 1972 T 6 S 379 394 DOI 10 1287 trsc 6 4 379 Z Drezner S Shelah On the complexity of the Elzinga Hearn algorithm for the 1 center problem 1987 T 12 vip 2 S 255 261 DOI 10 1287 moor 12 2 255 D W Hearn J Vijay S Nickel Codes of geometrical algorithms for the weighted minimum circle problem European Journal of Operational Research 1995 T 80 DOI 10 1016 0377 2217 95 90075 6 S K Jacobsen An algorithm for the minimax Weber problem European Journal of Operational Research 1981 T 6 DOI 10 1016 0377 2217 81 90200 9 D W Hearn J Vijay Efficient algorithms for the weighted minimum circle problem 1982 T 30 vip 4 DOI 10 1287 opre 30 4 777 J Elzinga D W Hearn W D Randolph Minimax multifacility location with Euclidean distances 1976 T 10 DOI 10 1287 trsc 10 4 321 C L Lawson The smallest covering cone or sphere 1965 T 7 vip 3 DOI 10 1137 1007084 M I Shamos D Hoey 1975 DOI 10 1109 SFCS 1975 8 N Megiddo The weighted Euclidean 1 center problem 1983 T 8 DOI 10 1287 moor 8 4 498 N Megiddo E Zemel An O n log n randomizing algorithm for the weighted Euclidean 1 center problem Journal of Algorithms 1986 T 7 DOI 10 1016 0196 6774 86 90027 1 PosilannyaBernd Gartner s smallest enclosing ball code 31 serpnya 2009 u Wayback Machine CGAL 24 veresnya 2013 u Wayback Machine pakunok Min sphere of spheres u Biblioteci algoritmiv obchislyuvalnoyi geometriyi Computational Geometry Algorithms Library CGAL Miniball 30 travnya 2022 u Wayback Machine realizaciya z vidkritimi sircyami algoritmu dlya zadachi pro najmenshu obmezhuvalnu kulyu dlya nizkih i pomirno visokih rozmirnostej

Дата публікації:
Топ