We study sublinear time complexity and algorithm to approximate the diameter for a sequence S = p_1p_2 ··· p_n of points in a metric space, in which every pair of two consecutive points p_i and P_i+1 in the sequence S has the same distance. The diameter of S is the largest distance between two points p_i and p_j in S. The approximate diameter problem is investigated under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations about the sublinear time computations using various versions of the approximate diameter problem based on the restriction about the format of input data.
展开▼
