Cubriendo un polígono simple con círculos

10

Supongamos que tengo un polígono simple y un entero . ¿Cuáles son algunos enfoques existentes para encontrar el radio más pequeño de modo que pueda cubrir con círculos de radio ? ¿Qué tal si es fijo y quiero minimizar ?k r S k r r kSkrSkrrk

cg.comp-geom planar-graphs set-cover usuario771871
fuente

Respuestas:

11

Utilice el algoritmo de agrupación de k-center: consulte la Sección 4.2 en http://goo.gl/pLiEO .

Se puede obtener un algoritmo de aproximación 1 + eps utilizando cuadrículas deslizantes.

Es natural suponer que el problema es NP-Hard debido al trabajo de Feder y Greene.

Sariel Har-Peled
fuente
1
Eso es lo que te da la rejilla deslizante ...
Sariel Har-Peled
Gracias por su respuesta. Estoy más o menos familiarizado con las rejillas deslizantes. En el escenario de puntos, se basa crucialmente en el hecho de que en cada celda de la cuadrícula se puede resolver el problema de cobertura de manera óptima ya que cada disco contiene dos puntos en su límite, más el número de discos para cubrir la celda. Por lo tanto, se puede resolver la fuerza bruta. Pero en la configuración de un polígono, no veo cómo resolver el problema en una celda de cuadrícula de manera óptima. ¿Te importaría dar algunas pistas sobre esto?
101011
Las rejillas deslizantes implican que dentro de la celda de la rejilla el tamaño de la solución es pequeño. Luego, debe resolver el problema dentro de cada celda de la cuadrícula (generalmente exactamente) utilizando algún otro algoritmo. Aquí hay una forma alternativa de pensarlo: muestrear el polígono muy densamente y luego resolver su problema en la muestra ... Y sí, los detalles exactos de cómo hacerlo podrían ser bastante dolorosos ... Entonces, suponga que tiene un polígono con n aristas, y sabes que la solución óptima es de tamaño k. ¿Sabes cómo resolver el problema exactamente en este caso?
Sariel Har-Peled
Gracias de nuevo. Después de pensar un poco más, todavía no sé cómo cubrir el polígono de manera óptima con k discos, incluso si sé k. El hecho de que haya poca naturaleza discreta hace que parezca realmente difícil para mí. En cuanto a su enfoque de muestreo: después del muestreo, ¿le gustaría cubrir solo la parte muestreada? ¿No nos encontramos entonces con el problema de desperdiciar muchos discos para llenar los vacíos?
101011
1
Considera el cuadrado. Cúbralo con una cuadrícula , para . Es fácil demostrar que cualquier k disco que cubra todos estos puntos, cubriría todo el cuadrado después de expandir cada disco en fracción de su radio. En cuanto al polígono, triangúlelo, forme una cuadrícula como la anterior para cada triángulo (esto requiere un poco de cuidado, pero no es especialmente difícil). Entonces obtienes la misma garantía, si tomas la unión de todos estos conjuntos de puntos. Esto es similar a la construcción de núcleo para la agrupación de k-center. N = O ( k / ϵ ) ϵN×NN=O(k/ϵ)ϵ
Sariel Har-Peled