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

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

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

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

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

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

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

Див. також

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