We study a generalization of the famous k-center problem where each object is an affine subspace of dimension Δ, and give either the first or significantly improved algorithms and hardness results for many combinations of parameters. This generalization from points (Δ=0) is motivated by the analysis of incomplete data, a pervasive challenge in statistics: incomplete data objects in Rd can be modeled as affine subspaces. We give three algorithmic results for different values of k,...