mindistpq

Mindistpq is a term used in computational geometry and metric space theory to denote the minimum distance between two point sets P and Q. It is defined as mindistpq(P, Q) = min{ d(p, q) : p ∈ P, q ∈ Q }, where d is a chosen metric. In Euclidean space with the standard distance, this specializes to the smallest Euclidean distance between a point of P and a point of Q. If P and Q share a point, mindistpq is 0. The quantity is symmetric: mindistpq(P, Q) = mindistpq(Q, P).

Computation for finite P and Q in Euclidean space under the Euclidean metric often starts with a naïve approach that tests every pair, giving a time complexity of O(|P||Q|). Practical methods use spatial data structures such as kd-trees, ball trees, or Voronoi-based approaches to prune candidate pairs and achieve subquadratic performance. In high dimensions, approximate methods or locality-sensitive hashing can provide faster estimates at the cost of accuracy. The problem can also be formulated as a constrained optimization problem, solvable with standard nonlinear programming techniques when the distance function is differentiable.

Variants and relationships: Mindistpq relates to other distance measures. The directed minimum distance from P to Q is mindistpq(P, Q) with the same definition; the Hausdorff distance uses the maximum of such distances rather than the minimum. Mindistpq generalizes to distances between curves, surfaces, or distributions under various norms (L2, L1, Linf).

Applications: Used in collision detection and clearance estimation in robotics, path planning, shape matching and model validation in computer vision, and geographic information systems to quantify separation between regions or features.