If regions are filled (not just random set of points), minimal distance between regions will be between 2 points on borders of this two regions. So in first step filter points of regions to find only those one on border (O(4m + 4n) "if") and then do brute force on borders. In 2d space border points count will be equal to something about sqrt(m). So resulting alghorithm will have complexity O(2*(sqrt(m) + sqrt(n))).