Before revision: Some researchers have proposed using non-Euclidean metrics for clustering data points . Generally, the metric should recognize that two points in the same cluster are close , even if their Euclidean distance is far.
After revision: We consider a simple graph-based metric on points in Euclidean space known as the edge-squared metric. This metric is defined by squaring the Euclidean distance between points, and taking the shortest paths on the resulting graph. This metric has been studied before in wireless networks and machine learning, and has the density sensitive property: distances between two points in the same cluster are close , even if their Euclidean distance is far.