Question

Given 3 sets of points choose one point in each set such that it has minimum perimeter

Answer 1

hlo mate ✌️

1) perform Delaunay triangluation - O(n log n), so we get a planar graph.

As it is Delaunay triangluation, which maximises the minimum angle, it is clear that the closest 3 points must be connected by at least 2 edges (but they don't necessarily need to form the triangle!). Otherwise there would be more closer points or more closed angles.

Hope it helps.