Given a set of points in 2-space, how hard is it to find the smallest number of lines such that at least one line goes through each point?
This problem was proven to be NP-complete in 1982 by Megiddo and Tamir [1]. The proof can be found in a paper by Arkin, Mitchell, and Piatko [PDF]. Bob Hearn came up with an alternate NP-completeness proof independent of this. His proof reduces SAT to the Line Cover problem.
[1] N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Oper. Res. Lett., 1:194-197, 1982.
Thanks to Mohammad Safari for locating this result.