My research corner

Sunday, April 09, 2006

\eps-net

An \eps-net for a metric space (e.g., a finiate metric space, Euclidean space, etc) is a subset S such that every two points in S are of distance \eps away; and every point is within distance \eps from at least one point from S.

A greedy algorithm can be used to generate such an \eps-net in a finite metric space. Pick a point not covered yet, add to S and continue.

Now my questions is to find an \eps-net efficiently for a unit ball in R^d.

0 Comments:

Post a Comment

<< Home