Closest pair

Questions 1 to 5 of 6

1. 1. What is the running time of the simple method that measures the distance between every pair of n points?

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

   O(n^2)O(n log n)O(n)O(n^2 log n)
3. 3. Why does each point in the strip need at most 7 comparisons with the points after it?

   The box above the point can hold at most 8 points, one per small square, so at most 7 others are checked.The strip is sorted by x, so only the first 7 points are close enough.The distance d is always exactly 7 units.The loop stops after 7 steps by design, whatever the input.
4. 4. Why did the third example return 2.0 instead of 1.414?

   The strip was built around the wrong cut line.The distance function uses only the y values.The loop started from C, so it never compared C with A.The strip was not sorted by y, so the loop stopped at B and never compared A with C.
5. 5. True or False: if the strip check is left out, the method can return a distance that is too large.

   False, because the two half answers always include the closest pair.True, because a pair with one point on each side of the cut is never checked.