Closest pair in Python

Questions 1 to 5 of 6

1. 1. In the strip step, the loop stops when strip[b].y - strip[a].y >= best. Why is it safe to stop there?

   The strip is sorted by x, so later points are farther away in xThe strip is sorted by y, so every later point has a y gap at least this big and is at least best awaybest only grows during the loop, so no later pair can beat itThe loop has already compared every pair in the strip
2. 2. Take one point in the strip. At most how many points that come after it in y order can be within d of it?

   3587
3. 3. What is the running time of checking every pair of n points, the brute force method used by brute_force in this lesson?

   O(n)O(n log n)O(n^2)O(2^n)
4. 4. What is the running time of the divide and conquer closest pair method from this lesson?

   O(n)O(n^2)O(n log^2 n)O(n log n)
5. 5. True or false: solving the left half and the right half, then taking the smaller answer, always gives the closest pair. Give the reason for your answer.

   False, because a closest pair can have one point in each half, and only the strip step checks those pairsTrue, because each half holds all the points that are near the dividing line