Optimizing $\epsilon$ in $\epsilon$-kernel

Question

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.

Answer 1

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....

Answer 2

This is a suggestion for some directions, rather than an answer.

The problem you ask seems closely related to the problem of polygon simplification (here's one possible starting point for tracking references) which comes in two flavors. The set up there is that you're given a polygon (or a curve for that matter) and you wish to simplify it. Your parameters are the error $\epsilon$ and the number of segments in the simplification $k$, and you can fix one or the other (the problem structure and solutions change accordingly).

If we consider the plane for now, here's an idea towards an approximation algorithm. Let's construct a subroutine that takes fixed parameters $\epsilon, k$ and determines whether an $\epsilon$-kernel exists. We will then binary search to get some approximation of the true $\epsilon$. We can do this because all we need to do is approximate the convex hull of the input point set, and if this convex hull size is strictly smaller than $k$, we can place a lower bound on $\epsilon$ (since at least some adjacent pair of edges in the hull will need to be shortcircuited).

So how to create the subroutine ? Firstly, if $\epsilon$ is the correct answer, then you know that the kernel's convex hull must lie within a "shrinking" of the original hull by $\epsilon$ (formally, by running a minkowski sum with a hemisphere of radius $\epsilon$ on the inside). Compute this region.

I'll then claim that a greedy strategy should work to verify whether you can solve the problem with $k$ points: the intuition is that convexity should ensure you don't need to backtrack. This idea comes from the polygonal simplification land.

Note that even if the above works, and I'm not more than 60% sure it will, it says nothing about hardness.