13.6.3. Scanning Points

Try these first

1. 1.

   Define the closest pair problem.

   Hint

   Think about what it means to measure distance.

2. 2.

   What is the time complexity of the brute-force method?

   Hint

   Recall how many combinations are formed by pairs.

3. 3.

   What is the main goal of the closest pair problem?

   • Find the farthest pair of points
   • Find the closest pair of points
   • Find the average distance between points

   Hint

   Focus on 'closest' versus 'farthest'.

4. 4.

   True or False: The brute-force method is optimal for large datasets.

   • True
   • False

   Hint

   Consider the nature of computational efficiency.

5. 5.

   Given a set of coordinates representing satellite locations, outline the plan using the divide and conquer method to determine the closest pair relevant for communication.

   Hint

   Think about how you would manage satellite data in two-dimensional space.

6. 6.

   Describe how the closest pair algorithm adapts when points can have equal x or y coordinates.

   Hint

   Consider how distance definitions change with duplicate points.