Optimizing $\epsilon$ in $\epsilon$-kernel 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 deﬁne 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 ﬁxed 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.
Jeff Philips has a related result showing the stability of kernels: http://www.cs.utah.edu/~jeffp/papers/stable-kernel.pdf.

As for the problem itself, it can be formulated as a hitting set problem. Indeed, you need to pick a point into the kernel for each "complement of a slab" that contains $\geq \epsilon_k$ fraction of the input points. Here $\epsilon_k$ is the minimum $\epsilon$ that has a kernel of size $k$. Since this is just a hitting set problem, it can be approximated up to $O( \log k)$ factor in geometric settings. You need to guess the value of $\epsilon_k$, but naively just do a binary search on epsilon. As such, one can get two results:


A set of size $O( k \log k)$ that is an $\epsilon_k$ kernel.
A set of size k that is  an $\epsilon_{O(k/\log k)}$ kernel.


The algorithm for computing the set cover is the reweighting algorithm. In fact, the original paper by Clarkson solves a related problem about polytope approximation:

@inproceedings{c-apca-93,
  author       = "Kenneth L. Clarkson",
  title        = "Algorithms for Polytope Covering and Approximation",
  booktitle    = "Proc. 3rd Workshop Algorithms Data Struct.",
  series       = LNCS,
  volume       = 709,
  publisher    = "Springer-Verlag",
  year         = 1993,
  pages        = "246--252"
}

As for what to implement, i would use an incremental algorithm that performs quite well in practice, and add points an incremental fashion. See for example, the paper "Robust Shape Fitting via Peeling and Grating Coresets" and references therein.

it seems believable BTW that one should be able to do constant factor approximation instead of logarithmic.

I dont know of a formal proof that this problem is NP-hard, but it would be very surprising if it is not, IMHO.

The problem is probably solvable exactly in the plane using dynamic programming, I think....