Um algoritmo eficiente é provavelmente aquele que faz uso de R-trees . O algoritmo seria algo como
type1RTree = new RTree()
for p1 in Type1Points
type1RTree.insert(p1)
min = inf
for p2 in Type2Points
nearest_p1 = type1RTree.nearest-neighbor(p2)
possibility = distance(p2, nearest_p1)
if possibility < min
min = possibility
output min
A maioria das linguagens deve ter uma implementação decente de R-tree em algum lugar; você também pode ver o artigo wiki vinculado para esboços de implementação de insert
e nearest-neighbor
.