13.1.1. Divide and Conquer: Closest Pair of Points

Try these first

1. 1.

   What is the time complexity of the brute-force approach for finding the closest pair of points?

   Hint

   Think about how many pairs you would check.

2. 2.

   What is the main assumption made for the points in the closest pair algorithm?

   Hint

   Consider how uniqueness helps in distance calculations.

3. 3.

   What is the time complexity of the closest pair of points using the divide and conquer approach?

   • O(n²)
   • O(n log n)
   • O(log n)

   Hint

   Think about the steps and their corresponding complexities.

4. 4.

   True or False: In the closest pair of points problem, we need to check every single point against every other point regardless of their position.

   • True
   • False

   Hint

   Consider how we split points.

5. 5.

   Given five points in a 2D space: (1,2), (3,1), (4,4), (5,3), and (2,5). Find the closest pair and use the divide and conquer method to justify your steps.

   Hint

   Carefully consider step-by-step pair comparisons both within each half and the band across the dividing line.

6. 6.

   How would you implement a function to perform the closest pair calculation on an arbitrary number of points?

   Hint

   Start with establishing base case handling and ensure effective recursion.