13.5.3. Points in the Zone

Try these first

1. 1.

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

   Hint

   Consider how many comparisons you're making with n points.

2. 2.

   Which formula is used to calculate the distance between two points in a 2D plane?

   Hint

   Think about the Pythagorean theorem.

3. 3.

   What is the main focus of the closest pair of points algorithm?

   • Finding the farthest points
   • Finding the closest pair of points
   • Sorting points

   Hint

   Think about the problem definition.

4. 4.

   The time complexity of the divide and conquer algorithm for finding the closest pair of points is:

   • True
   • False

   Hint

   Consider how sorting contributes to the complexity.

5. 5.

   Given a set of ten points, describe the steps you would take to implement the divide and conquer algorithm to find the closest pair.

   Hint

   Work through each step patiently.

6. 6.

   How does the existence of multiple points within a zone affect the accuracy of the closest pair distance?

   Hint

   Consider the relationship across the dividing line.