Největší prázdná koule - Largest empty sphere

Přerušovaná kružnice je obrys největší prázdné koule v těsné balení koulí. Viz také Intersticiální vada.
Nalezení největšího prázdného kruhu pomocí Voronoiho diagramu (dvě řešení).

v výpočetní geometrie, největší prázdná koule problém je problém najít a hypersféra největšího poloměru v d-rozměrný prostor, jehož vnitřek se nepřekrývá s danými překážkami.

Dva rozměry

The největší prázdný kruh problém je problém najít a kruh největšího poloměru v letadlo jehož vnitřek se nepřekrývá s danými překážkami.

Běžný speciální případ je následující. Dáno n bodů v rovině, najděte největší kruh uprostřed konvexní obal a žádný z nich neuzavřel. Problém lze vyřešit pomocí Voronoiovy diagramy v optimální čas .[1][2]

Viz také

Reference

  1. ^ G. T. Toussaint, „Výpočet největších prázdných kruhů s omezeními umístění“, International Journal of Computer and Information Sciences, sv. 12, č. 5, říjen 1983, str. 347-358.
  2. ^ Megan Schuster, „Největší problém prázdného kruhu“