13.5.2. Candidates for Overall Minimum Distance

Try these first

1. 1.

   What is the brute force approach to the closest pair problem?

   Hint

   Think about how many combinations of pairs there are.

2. 2.

   Define what is meant by 'divide and conquer' in algorithms?

   Hint

   Consider how you could solve a big problem by breaking it down.

3. 3.

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

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

   Hint

   Think about the efficiency gained when using sorting.

4. 4.

   True or False: Boundary candidates are irrelevant in finding the closest pair of points.

   • True
   • False

   Hint

   Consider if points only on one side could be the closest.

5. 5.

   If you were tasked with adapting the closest pair algorithm for a dynamic dataset where points can be added or removed frequently, how would you approach this problem?

   Hint

   Consider the implications of real-time changes on your sorting and dividing strategy.

6. 6.

   Develop a hypothetical scenario where the divide and conquer approach to closest pair would perform poorly compared to a brute-force approach.

   Hint

   Identify conditions under which sorting may not yield a straightforward advantage.