31/1/2000 - Well Separated Pairs Decomposition

Lecture is based on the paper:

Well Separated Pair Decomposition and Its Applications A decomposition of multidimensional point sets with applications to k nearest neighbors and n body potential fields
Paul Callahan and Rao Kosaraju

Journal of the ACM, Vol 42, No 1, January 19995, pp 67 90. online version

Slides in pdf format.

Click here to start

Table of contents

Computational Geometry

References

Definitions

Well Separated

Interaction Product of A and B

Well Separated Pair Decomposition

Fair Split Tree

Fair Split

Just the place for a figure...

Fair Split Trees

WSPD Algorithm

Lemma 4.1

Lemma 4.1 - Proof

Observations

Observations II

Result

Finding k-nearest neighbor

Lemma 8.2

Lemma 8.3

K Nearest Neighbor

Algorithm

Figure

Result