Expand description
§Well-Separated Pair Decomposition (WPSD)
This crate provides an efficient implementation of the Well-Separated Pair Decomposition data structure for geometric approximation algorithms.
§What is a WPSD
A Well-Separated Pair Decomposition (WSPD) is a way to partition all pairs of points in a d-dimensional point set into a smaller number of well-separated pairs. Two sets A and B are s-well separated if they can be enclosed in balls of equal radius r such that the distance between the balls is at least s * r.
The key insight is that for a point set of size n, we can represent all $\theta(n^2)$ pairs using only $O(s^d n)$ well-separated pairs, where d is the dimension and s is the separation factor.
Structs§
- Point2D
- A 2D point with explicit x and y coordinates.
- Point3D
- A 3D point with explicit x, y, and z coordinates.
- VecPoint
- A simple d-dimensional point implementation using a vector.
- WSPD
- WSPD
Builder - Builder for constructing a WSPD with custom parameters.
- WSPD
Stats - Statistics about the WSPD
- Well
Separated Pair - A well-separated pair in the decomposition.