Closest Pair

closest_pair.dart

import 'dart:math';

class ClosestPair {
  // O(n^2)
  static double bruteForce2D(List<Point> list) {
    double closest = double.infinity;
    
    for(var i = 0; i < list.length - 1; i++){
      for(var j = i + 1; j < list.length; j++){
        closest = min(closest, list[i].distanceTo(list[j]));
      }
    }
    return closest;
  }

  
  static double efficient2D(List<Point> list){
    List<Point> p = List<Point>.from(list);
    p.sort((a, b) => a.x.compareTo(b.x));
    
    List<Point> q = List<Point>.from(list);
    p.sort((a, b) => a.y.compareTo(b.y));
    
    return _efficient2DHelper(p, q);
  }
  
  
  // O(nlog(n)) 
  // Recurrence Relation: T(n) = 2T(n / 2) + f(n)
  static double _efficient2DHelper(List<Point> p, List<Point> q) {
    if (p.length <= 3) {
      return bruteForce2D(p);
    }

    List<Point> p_left = p.sublist(0, (p.length / 2).ceil());
    List<Point> q_left = q.sublist(0, (q.length / 2).ceil());
    List<Point> p_right = p.sublist((p.length / 2).floor());
    List<Point> q_right = q.sublist((q.length / 2).floor());

    double delta_left = _efficient2DHelper(p_left, q_left);
    double delta_right = _efficient2DHelper(p_right, q_right);

    double delta = min(delta_left, delta_right);

    int midpoint_x = p[(p.length / 2).ceil() - 1].x;

    List<Point> split =
        q.where((point) => (point.x - midpoint_x).abs() < delta).toList();

    double delta_min_square = delta * delta;

    for (var i = 0; i < split.length - 2; i++) {
      var k = i + 1;

      while (k <= split.length - 1 && pow(split[k].y - split[i].y, 2) < delta_min_square) {
        delta_min_square = min(split[k].squaredDistanceTo(split[i]), delta_min_square);
      }
    }
    
    return sqrt(delta_min_square);
  }
  
  // O(n^2)
  static num bruteForce1D(List<num> list){
    num closest = double.infinity;
    
    
    for(var i = 0; i < list.length - 1; i++){
      for(var j = i + 1; j < list.length; j++){
        closest = min(closest, (list[i] - list[j]).abs());
      }
    }
    return closest;
    
  }
  
  static num efficient1dDivideAndConquer(List<num> list){
    list.sort();
    return _efficient1dDivideAndConquerHelper(list, 0, list.length - 1);
  }
  
  static num _efficient1dDivideAndConquerHelper(List<num> list, int left, int right){
    if (left == right){
      return double.infinity;
    } else if (right - left == 1){
      return list[right] - list[left];
    } else {
      
      var temp = min(_efficient1dDivideAndConquerHelper(list, left, (left + right / 2).floor()),
                _efficient1dDivideAndConquerHelper(list, (left + right / 2).floor() + 1, right ));
      
      return min(temp, list[(left + right / 2).floor() + 1] - list[(left + right / 2).floor()]);
    }
    
  }
  
  // O(nlog(n)) = O(nlog(n)) + O(n)
  static num efficient1DSimple(List<num> list){
    num closest = double.infinity;
    
    // O(nlog(n))
    list.sort();
    
    // O(n)
    for(var i = 0; i < list.length - 1; i++){ 
      closest = min(closest, (list[i] - list[i + 1]).abs());
    }
    return closest;
  }
}


// Studying for an exam
// TODO: Test these functions
void main() {
}