Single-Link Merge Step

Problem

Find the single-link merge step: the pair of distinct clusters with the smallest minimum pairwise Euclidean distance between their members.

Return [label_a, label_b, distance] with label_a < label_b; ties in distance keep the first pair in sorted cluster order. Fewer than two clusters returns [].

Hint

Single linkage uses the closest pair of points across two clusters.

Test cases

case 1

in: [[[0,0],[1,0],[1.5,0],[5,5]],["a","a","b","c"]]

expected: ["a","b",0.5]

case 2

in: [[[0,0],[1,1],[4,4],[5,5]],[0,0,1,1]]

expected: [0,1,4.242640687119285]

case 3

in: [[[0,0],[1,1]],[9,9]]

expected: []

case 4

in: [[],[]]

expected: []

Starter codePython

def single_link_merge(points, labels):
    # Returns [label_a, label_b, distance]
    # Your code here
    pass

4 test cases · run your code against them in the editor