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

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

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

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

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

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

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття