The notion of $\epsilon$-kernel, as defined by Agarwal et al. ("Approximating extent measures of points"), is the following.
Let $S^{d−1}$ denote the unit sphere centered at the origin in $R^d$. For any set $P$ of points in $R^d$ and any direction $u \in S^{d−1}$, we define the directional width of $P$ in direction $u$, denoted by $\omega(u, P)$, to be
$\omega(u, P)=\max_{p\in P} \langle u, p \rangle - \min_{p\in P} \langle u, p \rangle$
where $\langle \cdot, \cdot\rangle $ is the standard inner product. Let $\epsilon > 0$ be a parameter. A subset $Q \subseteq P$ is called an $\epsilon$-kernel of $P$ if for each $u \in S^{d−1}$, $(1 − \epsilon)\omega(u, P) \leq \omega(u, Q)$.
It was shown that one can compute an $\epsilon$-kernel of $P$ of size $O(1/\epsilon^{(d−1)/2})$ in time $O(n + 1/\epsilon^{d−(3/2)})$. (Chan, "Faster coreset constructions and data stream algorithms in fixed dimensions".)
I am looking at the problem that is the reverse of this: Let $k$ be a parameter. I want to find an $\epsilon$-kernel of size at most $k$ such that $\epsilon$ is minimized. The running time could be exponential in $d$ but should be polynomial in $k$.
My general question is whether there is anything known for this problem. Some specific questions: 1. Is the problem NP-hard when d=2? (Any clue what problem we can reduce from?) 2. Is there any approximation algorithm for d=2?
Any general comments are also welcomed.