Subconjuntos máximos de un conjunto de puntos que caben en un disco unitario
Supongamos que hay un conjunto$P$de$n$puntos en el plano, y sea$P_1, \dots, P_k$ser subconjuntos distintos de$P$tal que todos los puntos en$P_i$cabe dentro de una unidad de disco para todos$i$,$1\le i\le k$.
Además, cada$P_i$es máxima, es decir, ningún disco unitario puede cubrir un subconjunto de$P$que es un superconjunto estricto de$P_i$. Visualmente hablando, si movemos un disco unitario que cubre$P_i$para cubrir un punto que no está en$P_i$, entonces al menos un punto que estaba dentro de ese disco quedará descubierto.
Aquí hay un ejemplo:
En la figura anterior, hay tres subconjuntos máximos.
No sé si este problema tiene un nombre o se estudió antes, pero aquí están mis preguntas.
- Pueden$k$ser exponencial con respecto a$n$?
- Si no, ¿podemos encontrar esos subconjuntos máximos en tiempo polinomial?$n$?
Creo que hay exponencialmente muchos de estos subconjuntos debido al siguiente argumento:
supongamos que los puntos son centros de algunos discos con radio$1/2$. Si un subconjunto de tales puntos cabe en un disco unitario, entonces forman una camarilla. Dado que hay exponencialmente muchas camarillas en un conjunto de discos, entonces debería haber exponencialmente muchos subconjuntos máximos de este conjunto particular de puntos que caben en una unidad de disco.
Respuestas
Definamos una función$f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, devolviendo un número de puntos del conjunto$P$, cubierto por un disco unitario con el centro en el punto$(x, y)$. Esta es una función constante por partes, y es fácil ver que su dominio puede pensarse como una subdivisión plana, definida por todas las intersecciones de discos unitarios, centrada en puntos del conjunto$P$. Esta subdivisión contiene vértices (= puntos de intersección), aristas (= arcos circulares) y caras (= partes del plano, donde la función$f$devuelve el mismo valor). Diremos que estas caras están etiquetadas por este valor.
Asumiremos que el gráfico plano, definido por esta subdivisión, es uno regular de 4 - es una suposición común, lo que significa que todos los puntos en$P$están en posición general (cada punto de intersección pertenece exactamente a dos círculos). Un ejemplo de tal subdivisión para$n=3$se encuentra a continuación, donde se muestra en color rojo la etiqueta de cada cara (incluida la externa).
Por lo que entiendo, tus subconjuntos máximos$P_i$se puede asociar con tales caras de esta subdivisión, que tienen etiquetas más grandes que todas las etiquetas de sus caras vecinas . Es una especie de interpretación estática de su semántica de "disco móvil", que utilizó en su definición del subconjunto máximo.
La subdivisión contendrá tantas caras como sea posible en el caso de que todos los círculos unitarios se intersequen por pares. Se puede demostrar que en este caso:
- número de vértices es$n(n-1)$
- número de aristas es$2n(n-1)$
- número de caras es$n(n-1)+2$
Entonces, las respuestas a sus preguntas serán:
- no, el numero$k$de subconjuntos máximos es$O(n^2)$, porque no puede ser más que el número de todas las caras.
- Sí, todos los subconjuntos máximos se pueden encontrar en$O(n^3)$tiempo mediante un algoritmo de escaneo ingenuo.
En cuanto al nombre de este problema, parece que puede estar relacionado con algunas variaciones del problema de la cubierta del disco de la unidad.