Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane.
My initial approach started like this, 1) for each point I note down the number of points in row and col. 2) Then for each point I check if (rows >= col) and if true, I mark that point as visited and all points in that corresponding row as visited. Else If (row < col), then I mark that point and the points in that col as visited.
But this approach would fail for the following cases,
In above case, according to my algo I end up with 3 lines. This is (rows >= col) condition. How do I deal when number of rows = cols. OR would my algo fail in other cases as well.
What is the correct approach for this question?
This can be reduced to the problem of finding a minimum vertex cover for a bipartite graph, which is equivalent to the maximum matching problem, for which a polynomial-time algorithm exists (the Hopcroft-Karp algorithm).
Let the points be given by $(x_i, y_i)$ for $i=1,2,\ldots,n$; denote the set of distinct $x$-values by $X$ and the set of distinct $y$-values by $Y$. Consider the bipartite graph whose nodes are the potential vertical and horizontal lines, $$V=\{v_x\;|\; x\in X\}\cup \{h_y \;|\; y\in Y\}$$ (where $v_x$ is the vertical line with $x$-coordinate $x$ and $h_y$ is the horizontal line with $y$-coordinate $y$), and where there is an edge $(v_{x_i}, h_{y_i})$ for each point $(x_i, y_i)$. So both $|V|$ and $|E|$ are $O(n)$. You are looking for the minimum number of lines (nodes) that cover all the points (are incident with all the edges). This is exactly the minimum vertex cover problem, which is NP-complete for general graphs, but is in P for bipartite graphs. As noted, this can be solved by finding a maximum-cardinality matching, which can be done in time $O(|E|\sqrt{|V|})=O(n^{3/2})$. If the maximum matching has $m$ edges, then (by König's theorem) the minimum vertex cover also has size $m$ (that is, $m$ lines are required to cover all the points).