13.3.1. Sorting and Finding Minimum Distance

Try these first

1. 1.

   What is the time complexity of the brute-force approach to find the closest pair of points?

   Hint

   Consider how many pairs you need to check.

2. 2.

   Why is sorting points necessary in the closest pair problem?

   Hint

   Think about how you might only need to check adjacent points.

3. 3.

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

   • O(n)
   • O(n log n)
   • O(n^2)
   • O(log n)

   Hint

   Consider how many total comparisons you must make.

4. 4.

   True or False: Sorting the points makes it easier to determine the closest pair by allowing us to check only adjacent points.

   • True
   • False

   Hint

   Think about how sorting affects the order of points.

5. 5.

   Suppose you have a set of 100 random points in a 2D space. How would you efficiently visualize the divide-and-conquer approach to find the closest points? Provide a detailed approach.

   Hint

   Use simple drawings to represent the steps.

6. 6.

   Consider a set of points where some are very close together and others are widely spaced. What pitfalls might arise in the brute-force approach, and how can divide-and-conquer mitigate these?

   Hint

   Think about the effectiveness of narrowing down your focus.