Número mínimo de líneas que cubre n puntos

Question

Let there be n puntos en el plano. Quiero saber el número mínimo de líneas horizontales y verticales que cubren todos los puntos en el plano.

Mi enfoque inicial comenzó como este, 1) por cada punto que anote el número de puntos en fila y col. 2) a Continuación, para cada punto de I compruebe si (filas >= col) y si es verdad, me marca ese punto como visitado y todos los puntos en que fila correspondiente como visitado. Else If (fila < col), y luego marcar el punto y los puntos en los que la col como visitado.

Pero este enfoque sería un error para los siguientes casos,

En el caso anterior, de acuerdo a mi algo me terminan con 3 líneas. Esto es (filas >= col) condición. ¿Qué hago cuando el número de filas = cols. O sería mi algo falla en otros casos.

¿Cuál es el enfoque correcto para esta pregunta?

Answer 1

Esto se puede reducir al problema de la búsqueda de un mínimo vértice de la cubierta de un bipartito gráfica, que es equivalente a la máxima coincidente del problema, para que un polinomio en tiempo del algoritmo existe ( Hopcroft-Karp algoritmo).

Vamos a los puntos dado por $(x_i, y_i)$$i=1,2,\ldots,n$; denota el conjunto de las distintas $x$-valores por $X$ y el conjunto de las distintas $y$-valores por $Y$. Considerar el bipartito grafo cuyos nodos son las posibles líneas verticales y horizontales, $$V=\{v_x\;|\; x\in X\}\cup \{h_y \;|\; y\in Y\}$$ (donde $v_x$ es la línea vertical con $x$-coordinar $x$ $h_y$ es la línea horizontal con $y$-coordinar $y$), y donde hay una ventaja $(v_{x_i}, h_{y_i})$ por cada punto de $(x_i, y_i)$. Por lo tanto $|V|$$|E|$$O(n)$. Estás buscando el mínimo número de líneas (nodos) que cubren todos los puntos (es el incidente con todos los bordes). Este es exactamente el mínimo vértice de la cubierta problema, que es NP-completo para el general de los gráficos, pero es en P para grafos bipartitos. Como se señaló, esto se puede resolver mediante la búsqueda de una máxima cardinalidad de coincidencia, que se puede hacer en el tiempo $O(|E|\sqrt{|V|})=O(n^{3/2})$. Si la máxima coincidencia de ha $m$ bordes, entonces (por la del teorema de König) el mínimo vértice de la cubierta también tiene el tamaño de $m$ (es decir, $m$ líneas son necesarios para cubrir todos los puntos).