You are given a set of points S in Euclidean space, as well as the distance of each point in S to a point x. (It does not matter if x ∈ S.)
(a) If the goal is to find all points within a specified distance ε of point y, y ≠ x, explain how you could use the triangle inequality and the already calculated distances to x to potentially reduce the number of distance calculations necessary? Hint: The triangle inequality, d(x, z) ≤ d(x, y) + d(y, x), can be rewritten as d(x, y) ≥ d(x, z) − d(y, z).
(b) In general, how would the distance between x and y affect the number of distance calculations?
(c) Suppose that you can find a small subset of points S′, from the original data set, such that every point in the data set is within a specified distance ε of at least one of the points in S′, and that you also have the pairwise distance matrix for S′. Describe a technique that uses this information to compute, with a minimum of distance calculations, the set of all points within a distance of β of a specified point from the data set.