Given n points where each point has its own range, adjust all points to maximize the minimum distance of adjacent points

Question

Take n points in one dimension:

Each point can be moved within a certain range indicated by the arrow above it. These ranges are known. Ranges can overlap. How can these points be adjusted so that minimum distance of adjacent points is maximized?

I would be okay with an approximation as well.

Edit: I am not really looking for code but a general strategy. I have really no idea how to solve this.

Originally, I thought a greedy algorithm might work.

1. Let p0 be the starting point and pn the ending point. Let dist(p0,p1) represent the distance between p0 and p1.Well obviously adjust p0 as far left as possible and pn as far right as possible.

2. Next, find dist(p0,pn)/n-1. This represents the optimal distance each point should be from each other to be as spread out as possible. Move p1 as close to this distance.

3. Find dist(p1, pn)/n-2. Move p2 as close to this distance as possible.

4. Repeat for rest of points.

This doesn't work because adjusting another pointer later on might ruin the previous points.

Answer 1

Here's some Ruby code, followed by sample results. The idea is to start with a random allocation of points to values within their ranges. Then we repeatedly do the following:

1. Find the minimum gap
2. Find all points that border a minimum gap
3. Re-randomize the values of those points

All the while, we remember the best solution so far. This won't give you the best possible result, but should give you a reasonably good result.

For the sample run, I gave a 'good' set of points by allocating 100 points evenly in a range of about 1100, then gave each point a range around that val. The algorithm was just given the ranges in random order. It's possible to get an input set of points where the best possible min gap is small or zero, which no algorithm can help with.

def test(n, range, max_attempts)
  points = get_points_with_optimal_min_gap(n, range)
  puts "input: #{points}"
  allocation = allocate_points(points, max_attempts)
  puts "solution: #{allocation.keys.sort}"
  puts "best gap: #{get_min_gap(allocation, points)}" 
  puts "\n\nallocation:"
  allocation.keys.sort.each do |k|
    puts "  #{k} => #{allocation[k]}"
  end
end

def get_points_with_optimal_min_gap(n, range)
  points = []
  1.upto(n) do |num|
    points.append([[0, num * range/n - rand(5*range/n)].max, num * range/n + rand(5*range/n)])
  end
  return points.shuffle
end




def allocate_points(input_points, max_attempts)
  val_to_points = Hash.new {|h, k| h[k] = []}
  input_points.each do |point|
    val = get_rand_val_for_point(point)
    val_to_points[val].append(point)
  end
  
  
  best_min_gap = -1
  best_allocation = nil
  attempts = 0
  while attempts < max_attempts do
    attempts += 1
    min_gap = get_min_gap(val_to_points, input_points)
    if min_gap > best_min_gap
      best_min_gap = min_gap
      best_allocation = deep_copy(val_to_points)
      puts "found new gap after #{attempts} tries: #{best_min_gap}"
      attempts = 0
    end
    vals_to_adjust = get_vals_bordering_min_gap(val_to_points, min_gap)
    points_to_reallocate = []
    vals_to_adjust.each do |val|
      points_to_reallocate += val_to_points.delete(val)
    end
  

    
    points_to_reallocate.each do |point|
      new_val = get_rand_val_for_point(point)
      val_to_points[new_val].append(point)
    end
  end
  return best_allocation
end


def get_vals_bordering_min_gap(val_to_points, min_gap)
  vals_bordering_min_gap = Set.new()
  if min_gap == 0
    val_to_points.each do |val, points|
      vals_bordering_min_gap.add(val) if points.size > 1
    end
  else
    sorted_vals = val_to_points.keys.sort
    
    prior_val = sorted_vals[0]
  
    1.upto(sorted_vals.size - 1) do |i|
      cur_val = sorted_vals[i]
      cur_gap = cur_val - prior_val
      if cur_gap == min_gap
        vals_bordering_min_gap.add(cur_val)
        vals_bordering_min_gap.add(prior_val)
      end
      prior_val = cur_val
    end
  end
  return vals_bordering_min_gap.to_a
end


def get_min_gap(val_to_points, input_points)
  return 0 if val_to_points.size < input_points.size
  
  sorted_vals = val_to_points.keys.sort
  prior_val = sorted_vals[0]
  
  min_gap = nil
  1.upto(sorted_vals.size - 1) do |i|
    cur_val = sorted_vals[i]
    min_gap = cur_val - prior_val if min_gap.nil? || cur_val - prior_val < min_gap
    prior_val = cur_val
    return min_gap if min_gap == 1
  end
  return min_gap
end


def get_rand_val_for_point(point)
  return point[0] + rand(point[1] - point[0] + 1)
end

def deep_copy(int_to_arr_of_int_pairs)
  new_hash = Hash.new {|h, k| h[k] = []}
  int_to_arr_of_int_pairs.each do |int, arr|
    arr.each do |int_pair|
      new_hash[int].append([int_pair[0], int_pair[1]])
    end
  end
  return new_hash
end

Sample Results

input: [[207, 258], [754, 826], [957, 993], [127, 158], [332, 352], [539, 615], [213, 236], [572, 590], [668, 712], [802, 823], [385, 427], [595, 641], [924, 1018], [20, 50], [698, 749], [318, 335], [64, 120], [462, 521], [708, 760], [513, 569], [806, 877], [364, 380], [732, 799], [896, 923], [947, 997], [250, 281], [798, 857], [717, 795], [542, 583], [910, 964], [277, 315], [168, 221], [263, 337], [858, 920], [316, 348], [646, 705], [557, 573], [293, 315], [48, 131], [488, 522], [252, 271], [269, 326], [43, 106], [673, 728], [399, 432], [140, 184], [564, 630], [906, 973], [508, 566], [0, 17], [493, 547], [782, 817], [184, 246], [230, 305], [5, 90], [446, 507], [429, 449], [822, 917], [35, 127], [630, 699], [888, 944], [899, 917], [179, 201], [715, 785], [40, 65], [338, 415], [908, 958], [2, 31], [469, 517], [649, 718], [96, 150], [380, 428], [347, 401], [197, 289], [849, 912], [603, 642], [805, 830], [564, 629], [19, 88], [80, 151], [593, 660], [932, 994], [479, 541], [291, 331], [175, 192], [842, 877], [987, 1028], [382, 432], [796, 884], [102, 160], [535, 587], [621, 696], [461, 476], [131, 170], [437, 469], [343, 410], [660, 713], [122, 171], [699, 752], [776, 782]]
found new gap after 1 tries: 0
found new gap after 2 tries: 1
found new gap after 8 tries: 2
found new gap after 9 tries: 3
found new gap after 35 tries: 4
found new gap after 87 tries: 5
found new gap after 384 tries: 6
found new gap after 8043 tries: 7
solution: [4, 12, 20, 31, 43, 51, 59, 68, 82, 102, 110, 119, 127, 134, 141, 148, 161, 172, 179, 188, 202, 209, 223, 233, 244, 251, 258, 273, 284, 299, 308, 326, 335, 344, 351, 361, 369, 376, 383, 395, 408, 415, 423, 430, 438, 454, 468, 482, 491, 499, 508, 515, 524, 532, 539, 549, 557, 574, 582, 589, 596, 615, 623, 634, 642, 649, 656, 663, 676, 693, 720, 728, 741, 748, 758, 769, 776, 786, 801, 808, 815, 827, 834, 842, 851, 858, 865, 872, 882, 899, 911, 935, 943, 952, 962, 974, 987, 996, 1011, 1028]
best gap: 7


allocation:
  4 => [[0, 17]]
  12 => [[5, 90]]
  20 => [[2, 31]]
  31 => [[20, 50]]
  43 => [[19, 88]]
  51 => [[40, 65]]
  59 => [[35, 127]]
  68 => [[43, 106]]
  82 => [[64, 120]]
  102 => [[96, 150]]
  110 => [[80, 151]]
  119 => [[48, 131]]
  127 => [[122, 171]]
  134 => [[102, 160]]
  141 => [[140, 184]]
  148 => [[127, 158]]
  161 => [[131, 170]]
  172 => [[168, 221]]
  179 => [[179, 201]]
  188 => [[175, 192]]
  202 => [[184, 246]]
  209 => [[207, 258]]
  223 => [[197, 289]]
  233 => [[213, 236]]
  244 => [[230, 305]]
  251 => [[250, 281]]
  258 => [[252, 271]]
  273 => [[263, 337]]
  284 => [[269, 326]]
  299 => [[277, 315]]
  308 => [[293, 315]]
  326 => [[291, 331]]
  335 => [[318, 335]]
  344 => [[316, 348]]
  351 => [[332, 352]]
  361 => [[347, 401]]
  369 => [[343, 410]]
  376 => [[364, 380]]
  383 => [[338, 415]]
  395 => [[382, 432]]
  408 => [[399, 432]]
  415 => [[380, 428]]
  423 => [[385, 427]]
  430 => [[429, 449]]
  438 => [[437, 469]]
  454 => [[446, 507]]
  468 => [[461, 476]]
  482 => [[479, 541]]
  491 => [[469, 517]]
  499 => [[462, 521]]
  508 => [[488, 522]]
  515 => [[493, 547]]
  524 => [[513, 569]]
  532 => [[508, 566]]
  539 => [[535, 587]]
  549 => [[539, 615]]
  557 => [[557, 573]]
  574 => [[542, 583]]
  582 => [[572, 590]]
  589 => [[564, 629]]
  596 => [[564, 630]]
  615 => [[595, 641]]
  623 => [[603, 642]]
  634 => [[630, 699]]
  642 => [[593, 660]]
  649 => [[621, 696]]
  656 => [[649, 718]]
  663 => [[646, 705]]
  676 => [[660, 713]]
  693 => [[668, 712]]
  720 => [[673, 728]]
  728 => [[699, 752]]
  741 => [[698, 749]]
  748 => [[717, 795]]
  758 => [[708, 760]]
  769 => [[715, 785]]
  776 => [[776, 782]]
  786 => [[732, 799]]
  801 => [[754, 826]]
  808 => [[802, 823]]
  815 => [[782, 817]]
  827 => [[805, 830]]
  834 => [[806, 877]]
  842 => [[796, 884]]
  851 => [[798, 857]]
  858 => [[822, 917]]
  865 => [[842, 877]]
  872 => [[858, 920]]
  882 => [[849, 912]]
  899 => [[899, 917]]
  911 => [[896, 923]]
  935 => [[906, 973]]
  943 => [[888, 944]]
  952 => [[908, 958]]
  962 => [[910, 964]]
  974 => [[957, 993]]
  987 => [[932, 994]]
  996 => [[947, 997]]
  1011 => [[924, 1018]]
  1028 => [[987, 1028]]

---- UPDATE ----

I added code to try to find the optimal gap for a given ordering. This is significantly better.

allocate_points() changed, and I added a new method called attempt_to_achieve_min_gap().

def attempt_to_achieve_min_gap(val_to_points, target_min_gap)
  new_val_to_points = Hash.new {|h, k| h[k] = []}
  
  leftmost_val = val_to_points.keys.min
  leftmost_point = val_to_points[leftmost_val][0]
  new_val_to_points[leftmost_point[0]].append(leftmost_point)
  
  sorted_vals = val_to_points.keys.sort
  prior_val = leftmost_val
  1.upto(sorted_vals.length - 1) do |i|
    cur_val = sorted_vals[i]
    cur_point = val_to_points[cur_val][0]
    target_val = prior_val + target_min_gap
    if target_val <= cur_point[0]
      new_val_to_points[cur_point[0]].append(cur_point)
      prior_val = cur_point[0]
    elsif target_val <= cur_point[1]
      new_val_to_points[target_val].append(cur_point)
      prior_val = target_val
    else
      return false
    end
  end
  return new_val_to_points
end


def allocate_points(input_points, max_attempts)
  val_to_points = Hash.new {|h, k| h[k] = []}
  input_points.each do |point|
    val = get_rand_val_for_point(point)
    val_to_points[val].append(point)
  end
  
  
  best_min_gap = -1
  best_allocation = nil
  attempts = 0
  while attempts < max_attempts do
    attempts += 1
    min_gap = get_min_gap(val_to_points, input_points)
    if min_gap > 0
      found_improvement = true
      while found_improvement
        found_improvement = false
        trial_min_gap = [min_gap, best_min_gap].max + 1
        improved_results = attempt_to_achieve_min_gap(val_to_points, trial_min_gap)
        if improved_results
          found_improvement = true
          min_gap = trial_min_gap
          puts "found improvement!: #{min_gap}"
          val_to_points = improved_results
        end
      end
    end
    if min_gap > best_min_gap
      best_min_gap = min_gap
      best_allocation = deep_copy(val_to_points)
      puts "found new gap after #{attempts} tries: #{best_min_gap}"
      attempts = 0
    end
    vals_to_adjust = get_vals_bordering_min_gap(val_to_points, min_gap)
    points_to_reallocate = []
    vals_to_adjust.each do |val|
      points_to_reallocate += val_to_points.delete(val)
    end
  

    
    points_to_reallocate.each do |point|
      new_val = get_rand_val_for_point(point)
      val_to_points[new_val].append(point)
    end
  end
  return best_allocation
end

New sample results:

input: [[0, 21], [787, 819], [614, 642], [503, 553], [771, 854], [701, 740], [768, 807], [475, 480], [223, 251], [431, 473], [19, 67], [711, 764], [650, 673], [381, 401], [832, 907], [303, 357], [414, 480], [201, 215], [130, 182], [233, 269], [335, 417], [637, 704], [193, 242], [566, 632], [854, 927], [545, 577], [548, 574], [552, 607], [812, 868], [949, 962], [290, 334], [299, 372], [0, 31], [234, 304], [488, 540], [132, 215], [975, 994], [389, 406], [378, 437], [685, 721], [410, 453], [750, 800], [856, 919], [237, 270], [322, 355], [964, 1018], [67, 90], [925, 1015], [736, 792], [755, 823], [29, 78], [709, 761], [828, 897], [873, 927], [464, 533], [332, 380], [788, 831], [354, 413], [500, 545], [144, 196], [96, 138], [925, 982], [0, 67], [183, 207], [83, 116], [665, 679], [843, 904], [654, 694], [892, 955], [179, 203], [56, 87], [575, 636], [484, 542], [380, 439], [592, 689], [419, 431], [654, 700], [907, 978], [136, 151], [242, 313], [96, 126], [975, 1023], [449, 491], [866, 924], [117, 177], [291, 351], [460, 485], [959, 1004], [797, 846], [210, 277], [207, 240], [138, 184], [536, 606], [710, 774], [695, 714], [71, 83], [617, 629], [284, 302], [576, 633], [88, 137]]
found new gap after 1 tries: 0
found improvement!: 2
found improvement!: 3
found improvement!: 4
found improvement!: 5
found improvement!: 6
found new gap after 1 tries: 6
found improvement!: 7
found new gap after 5 tries: 7
found improvement!: 8
found improvement!: 9
found new gap after 2 tries: 9
found improvement!: 10
found new gap after 5686 tries: 10
solution: [0, 12, 22, 32, 42, 56, 67, 77, 87, 97, 107, 117, 127, 137, 147, 157, 167, 177, 187, 197, 207, 217, 227, 237, 247, 257, 267, 277, 287, 297, 307, 317, 327, 337, 347, 357, 367, 377, 389, 399, 409, 419, 429, 439, 449, 459, 469, 479, 489, 499, 509, 519, 529, 539, 549, 559, 569, 579, 589, 599, 614, 624, 634, 644, 654, 664, 674, 684, 694, 704, 714, 724, 734, 744, 754, 764, 774, 784, 794, 804, 814, 824, 834, 844, 854, 864, 874, 884, 894, 904, 914, 925, 935, 949, 959, 975, 985, 995, 1005, 1015]
best gap: 10


allocation:
  0 => [[0, 31]]
  12 => [[0, 21]]
  22 => [[0, 67]]
  32 => [[19, 67]]
  42 => [[29, 78]]
  56 => [[56, 87]]
  67 => [[67, 90]]
  77 => [[71, 83]]
  87 => [[83, 116]]
  97 => [[88, 137]]
  107 => [[96, 126]]
  117 => [[117, 177]]
  127 => [[96, 138]]
  137 => [[132, 215]]
  147 => [[136, 151]]
  157 => [[144, 196]]
  167 => [[130, 182]]
  177 => [[138, 184]]
  187 => [[179, 203]]
  197 => [[183, 207]]
  207 => [[201, 215]]
  217 => [[207, 240]]
  227 => [[223, 251]]
  237 => [[193, 242]]
  247 => [[237, 270]]
  257 => [[210, 277]]
  267 => [[233, 269]]
  277 => [[234, 304]]
  287 => [[242, 313]]
  297 => [[284, 302]]
  307 => [[291, 351]]
  317 => [[290, 334]]
  327 => [[303, 357]]
  337 => [[322, 355]]
  347 => [[299, 372]]
  357 => [[354, 413]]
  367 => [[335, 417]]
  377 => [[332, 380]]
  389 => [[389, 406]]
  399 => [[381, 401]]
  409 => [[378, 437]]
  419 => [[419, 431]]
  429 => [[380, 439]]
  439 => [[410, 453]]
  449 => [[431, 473]]
  459 => [[414, 480]]
  469 => [[460, 485]]
  479 => [[475, 480]]
  489 => [[449, 491]]
  499 => [[464, 533]]
  509 => [[488, 540]]
  519 => [[484, 542]]
  529 => [[500, 545]]
  539 => [[503, 553]]
  549 => [[545, 577]]
  559 => [[548, 574]]
  569 => [[566, 632]]
  579 => [[552, 607]]
  589 => [[536, 606]]
  599 => [[576, 633]]
  614 => [[614, 642]]
  624 => [[617, 629]]
  634 => [[575, 636]]
  644 => [[592, 689]]
  654 => [[650, 673]]
  664 => [[637, 704]]
  674 => [[665, 679]]
  684 => [[654, 694]]
  694 => [[654, 700]]
  704 => [[695, 714]]
  714 => [[685, 721]]
  724 => [[709, 761]]
  734 => [[701, 740]]
  744 => [[711, 764]]
  754 => [[750, 800]]
  764 => [[710, 774]]
  774 => [[768, 807]]
  784 => [[736, 792]]
  794 => [[787, 819]]
  804 => [[755, 823]]
  814 => [[788, 831]]
  824 => [[771, 854]]
  834 => [[797, 846]]
  844 => [[812, 868]]
  854 => [[828, 897]]
  864 => [[832, 907]]
  874 => [[843, 904]]
  884 => [[866, 924]]
  894 => [[873, 927]]
  904 => [[856, 919]]
  914 => [[854, 927]]
  925 => [[925, 982]]
  935 => [[892, 955]]
  949 => [[949, 962]]
  959 => [[907, 978]]
  975 => [[975, 994]]
  985 => [[964, 1018]]
  995 => [[959, 1004]]
  1005 => [[925, 1015]]
  1015 => [[975, 1023]]