-
Metric Space $epsilon$-Nets and Their Applications
Ken Clarkson
-
Metric Spaces
- A metric space is a collection of points `U` and a distance measure `D` so that:
- `D(x,y)=0 iff x=y`;
- `D(x,y)=D(y,x)`;
- `D(x,z) <= D(x,y) + D(y,z)`
- Examples:
- Nodes in a graph
- Pixels in an image
- Points on a surface
- Functions
-
Test
sum= 0 rms= 0
-
Packings, Coverings, and Nets
- Subsets of the points that are "nicely distributed";
- `S` is a:
- Covering if every point in `U` has some point in `S` nearby
- Packing if no pairs of points in `S` is too close together;
- Net or Delone Set if `S` is both a covering and a packing
- Delone `equiv` Delaunay `equiv` Делоне
-
Building Nets: the Greedy Algorithm
- Nets exist: here's a simple greedy algorithm:
- Pick any point, put in N;
- Repeat until have `k` points:
- Pick the point in `S setminus N` farthest from `N`, add to `N`
- <Demo: animation of algorithm>
-
The Greedy Algorithm, more
- Optimal approximation algorithm, in a sense;
- Also called, for example:
- Bawden-Lajiness algorithm in computational chemistry;
- Farthest Point Sampling in Image Processing (Eldar et al.
- Used to build data structures for nearest neighbor searching [Bri95][WOj03][C03][HPM05]
- Due to Kolmogorov/Tikhonov?
-
Nets as "Beacons" or "Landmarks"
- In networks: pick a net `N`;
- To route from `a->b`:
- Let `hat a` be nearest to `a` in `N`
- Let `hat b` nearest to `b` in `N`
- Walk `a -> hat a -> hat b -> b
- Simpler addressing, simpler network
- <Picture>
-
Nets as Roadmaps: Motion Planning
- Consider moving a small object (a point) among obstacles
- By using more dimensions, can model more complicated motions and objects
-
Nets as (Non)-Probabalistic Roadmaps
- Original Approach:
- Pick configuration points at random;
- Find straight-line paths between nearby points
- Random points are nice; `epsilon`-nets are nicer
- (Sobol sets are even better?)
-
Nets as Roadmaps, Analysis
- Consider case where shortest path from `a` to `b` is continuous
- Suppose `N` is a `delta^2`-net, `delta ≤ 1`
- Suppose every `a,b in N` with `D(a,b)≤2delta` are connected
- Then this scheme gives `1+delta` approximation:
- Split path into segments of length `delta`
- Using triangle inequality, path in `N` has `≤ delta` overhead
-
Nearest Neighbor Searching
- Given `(S,D)`, `S subset U`, `diam S =1`
- Build a data structure so that for `q in U`, can find nearest `a in S`
- Divide-and-conquer approach for approximation algorithm:
- Find `delta^2`-net `N`;
- Recursively build data structure for each `S_p := B(p, 2delta) cap S`
- To search: given `q`, find nearest `p in N`; recursively search `S_p`
-
Nearest Neighbor Searching, II
- Suppose `N` is a `delta^2`-net, `delta ≤ 1`
- `a` has some `p_a in N` within `delta^2`, so `D(q, p_a) ≤ D(q,a) + delta^2`
- Suppose `p in N` is closest in `q` in `N` (no farther than `p_a`)
- Then either:
- `D(q,a)>=delta`, so `p` is within `1+delta` of closest, or
- `D(q,a) ≤ delta`, and nearest to `q` is in `B(p, 2delta)`
- Recursively, look in `B(p, 2delta) cap S`
-
Nets as Vertices in Approximations
- Polygonal approximation of smooth curves:
- Pick a good distance measure;
- Pick an `epsilon`-net of points on the curve;
- Connect the dots
- Due to McClure/Vitale, 1975
-
What Distance Measure?
- Arc Length: not always good;
- Should adapt to curvature
- Use `sqrt {:kappa(x):}` as a weight for distance, where
- `kappa(x)` is the curvature
- <picture>
-
Nets as Vertices of Graded Triangulations
- A way of approximating surfaces that are graphs of functions
- Triangulate a region, use function value at vertices, linearly interpolate
- Triangles should:
- be close to equilateral;
- conform to the boundary of the region;
- Implies a "local feature size" `F(a)` at point `a`
-
A Metric Space Scaled to LFS
- There is a distance measure $D_F$ so that:
- `D_F(a,b) approx D(a,b)/F(a)` when `D_F` is small
- Greedy algorithm then very close to Chew's algorithm
-
The Biotope Transform
- The distance measure `D_F` is built using the
biotope transform:
Given `a in U`, the biotope
or Steinhaus transform
`hat D(x,y) := {:2D(x,y):} / {:D(x,a) + D(y,a) + D(x,y):}
yields a metric.
For `D(A,B)=mu(A Delta B)` and `a=O/`, get
`hat D(A,B) = {:mu(A Delta B):} / {:mu(A uu B):}`
Replacing `D(x,a) + D(y,a)` by `min_{a in T} D(x,a) + D(y,a)` also gives a metric,
for `T subset U`.
-
Scaling by Distance to Boundary
- Using a circle as the subset `T`, we get a space similar to the Poincaire disk model of hyperbolic space:
- <Picture> <Escher pic?>
-
`epsilon`-nets as approximations to other measures
- `D(p, N) := min_{p' in N} D(p,p')`
- While `epsilon`-net `N` minimizes
`max_{p in S} D(p,N)`
- How about minimizing
`sum_{p in S} D(p,N)^2` ?
- In the smooth case, `epsilon`-nets are also pretty good for the latter
-
`epsilon`-nets for `k`-means
- Suppose `U` is a space for which $vol B(x,r) \approx r^d$, for all $x\in U$
- Then if `S` is not a covering, it cannot be optimal for sum-of-squares
- We can "pivot": remove a member of `S`, add a new point to `S` far from others
- Ditto if `S` is not a packing
- ....animation....