Voronoi trees and clustering problems

摘要

This paper presents a new data structure called Voronoi trees to support the solution of proximity problems in general quasi-metric spaces with efficiently computable distance functions. We analyze some structural properties and report experimental results showing that Voronoi trees are a proper and very efficient tool for the representation of proximity properties and generation of suitable clusterings.