Metric trees (sometimes called ball trees) are a simple generalization of this to arbitrary metrics. They're also useful for points in a high dimensional euclidean space that have low intrinsic dimensionality.