Transforming Hierarchical Trees on Metric Spaces
The Canadian Conference on Computational Geometry, Vancouver, Canada, August 4, 2016
We show how a simple hierarchical tree called a cover tree can be turned into an asymptotically more efficient one known as a net-tree in linear time. We also introduce two linear-time operations to manipulate cover trees called coarsening and refining. These operations make a trade-off between tree height and the node degree.