Найбільша порожня сфера

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

Знаходження найбільшого порожнього кола за допомогою діаграми Вороного (два розв'язки).

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

Двовимірний простір

Задача про найбі́льше поро́жнє ко́ло — це задача знаходження кола найбільшого радіуса на площині, внутрішність якого не перекриває жодної із заданих перешкод.

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

Див. також

• Обмежувальна сфера
• Перехід до найвіддаленіших
• Задача про найбільший порожній прямокутник

Література

• Toussaint G. T. Computing largest empty circles with location constraints // International Journal of Computer and Information Sciences. — 1983. — Т. 12, вип. 5 (October).
• Megan Schuster. The Largest Empty Circle Problem.