Some researchers have proposed using non-Euclidean metrics for clusteringdata points. Generally, the metric should recognize that two points in the samecluster are close, even if their Euclidean distance is far. Multiple proposalshave been suggested, including the Edge-Squared Metric (a specific example of agraph geodesic) and the Nearest Neighbor Metric. In this paper, we prove that the edge-squared and nearest-neighbor metricsare in fact equivalent. Previous best work showed that the edge-squared metricwas a 3-approximation of the Nearest Neighbor metric. This paper represents oneof the first proofs of equating a continuous metric with a discrete metric,using non-trivial discrete methods. Our proof uses the Kirszbraun theorem (alsoknown as the Lipschitz Extension Theorem and Brehm's Extension Theorem), anotable theorem in functional analysis and computational geometry. The results of our paper, combined with the results of Hwang, Damelin, andHero, tell us that the Nearest Neighbor distance on i.i.d samples of a densityis a reasonable constant approximation of a natural density-based distancefunction.
展开▼
