Relaxing the Triangle Inequality in Pattern Matching

Any notion of closeness in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality (d(A,C) < d(A, B) + d(B,C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a relaxed triangle inequality siffices, of the form d(A,C) < c(d(A,B) + d(B,C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in IBM's QBIC (Query by Image Content) system satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.