7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Part of the definition of ω(u,P) seems to be missing (although I can imagine what should be written). Please verify that your question is posted as you intended, because posts are sometimes garbled because of some kind of technical limitation, which I know little about. $\endgroup$ – Tsuyoshi Ito Sep 16 '10 at 11:50
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ... you need to pick a point into the kernel for each "complement of a slab"... Could you elaborate this point or give some references please? $\endgroup$ – Danu Sep 19 '10 at 9:21
  • 1
    $\begingroup$ Sure. Consider a direction $v$, and consider the projection of the point set into the line spanned in the direction of v. Consider the smallest interval, say $I$, that contains the projected points on this line. Now, consider any interval $J$ that is contained inside $I$, such that $len(J) < (1-\eps)len(I)$. Such an interval defines a slab $S_J$ (i.e., consider the region between the two hyperplanes passing through the endpoints of $I$ that are perpendicular to $v$). Clearly, the kernel must contain a point outside $S_J$. Otherwise, is a dir (i.e., $v$) for which the $\epsilon$-kernel fails. $\endgroup$ – Sariel Har-Peled Sep 22 '10 at 0:07
  • $\begingroup$ Thank you for your answer and clarification! So I guess the conclusion is the following (please correct me if I'm wrong). We can get $\log k $-approximation in the sense of output size or get $\epsilon_{k/\log k}$ instead of $\epsilon_k$. However, approximating $\epsilon_k$ while maintaining the output size to be $k$ is still open. It's not even known if the problem is NP-hard. (It should be in general but it might not be in the case of plane.) $\endgroup$ – Danu Oct 2 '10 at 13:29
  • $\begingroup$ Yes. Thats the state as far as I know it. $\endgroup$ – Sariel Har-Peled Oct 3 '10 at 6:49
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.