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