kd: Use a more traditional k-d tree implementation

The slight extra pruning possible in the previous implementation didn't
seem to be worth it.  The new, simpler implementation is also about 30%
faster in most of the benchmarks.

This gets rid of Coordinate{Proximity,Metric} as they're not necessary
any more (and the old ExactNeighbors impl was too restrictive anyway).

1 files changed, 16 insertions, 3 deletions

diff --git a/src/lp.rs b/src/lp.rs
index 4afd209..db9e65c 100644
--- a/src/lp.rs
+++ b/src/lp.rs
@@ -1,6 +1,10 @@
-//! [`$L^p$` spaces](https://en.wikipedia.org/wiki/Lp_space).
+//! [`$\ell^p$`]/[Minkowski] distance.
+//!
+//! [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
+//! [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance
 
 use crate::coords::Coordinates;
+use crate::distance::Proximity;
 
 use num_traits::real::Real;
 use num_traits::zero;
@@ -25,7 +29,7 @@ pub use crate::chebyshev::Chebyshev as Linf;
 /// Compute the L<sup>∞</sup> distance between two points.
 pub use crate::chebyshev::chebyshev_distance as linf_distance;
 
-/// Compute the [`$L^p$` distance] between two points.
+/// Compute the [`$\ell^p$`]/[Minkowski] distance between two points.
 ///
 /// ```math
 /// \begin{aligned}
@@ -34,7 +38,8 @@ pub use crate::chebyshev::chebyshev_distance as linf_distance;
 /// \end{aligned}
 /// ```
 ///
-/// [`$L^p$` distance]: https://en.wikipedia.org/wiki/Lp_space
+/// [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
+/// [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance
 pub fn lp_distance<T, U>(p: T::Value, x: T, y: U) -> T::Value
 where
     T: Coordinates,
@@ -51,6 +56,14 @@ where
     sum.powf(p.recip())
 }
 
+/// Marker trait for [Minkowski distances].
+///
+/// [Minkowski distances]: https://en.wikipedia.org/wiki/Minkowski_distance
+pub trait Minkowski<T: ?Sized = Self>: Proximity<T> {}
+
+/// Blanket [`Minkowski`] implementation for references.
+impl<'k, 'v, K: Minkowski<V>, V> Minkowski<&'v V> for &'k K {}
+
 #[cfg(test)]
 mod tests {
     use super::*;