Use this GitHub Classroom link to get started: classroom.github.com/a/5jehf_QK.

Don't edit the test file yet. The tests are still a work in progress. If you want to add tests now, put them in a separate .cpp file.

The Challenge

Implement a divide and conquer algorithm for determining which points in a set are the closest. The algorithm will be similar to the one presented in class, with three additions:

• There can be ties.
• You must return the pairs of closets points (not just determine the minimum distance).
• Your algorithm will take a tolerance parameter that determines the threshold for determining a "tie".

Details

Implement the following two methods:

• static PointPairSet closestPairsBruteForce(const PointVector &pairs, double tolerance = 0.000001)
• static PointPairSet closestPairs(const PointVector &pairs, double tolerance = 0.000001)

• closestPairsBruteForce will just compare all O(n^2) pairs of points and return the sets that are the closest. Implementing this function will help you work out the details of managing ties -- especially with respect to the tolerance.
• closestPairs must be a O(n log n) divide and conquer algorithm. (Note: The O(n log n) bound applies only to inputs with no ties.)
• The following data types are defined in ClosestPairs.h. You must use them in the signature of the above methods, otherwise my tests won't run:
  • Point: Represents an (x, y) point. It's just a renaming of std::pair<double, double>.
  • PointVector: A list of Points. It's just a renaming of std::vector<Point>.
  • PointPair: A pair of Points. Used to represent two points that are part of the answer. It's just a renaming of std::pair<Point, Point>.
  • PointPairSet: A set of PointPairs. Since there can be a tie for closest points, the closestPairs methods return a set of PointPairs.
• The return values for the closetPairs methods must order the points within each PointPair in lexicographic order. (In other words, sort by x coordinate, then by y coordinate. If the closest points are (5, 15) and (10, 6), then they should appear in the PointPair as {{5, 15}, {10, 6}}.) The tests will fail if PointPairs are in the wrong order.
• The closetPairs methods should return all pairs of points whose distance is within tolerance of the minimum. Important: Think carefully about this: Only include pairs whose distance is withing tolerance of the minimum. Don't apply it transitively to all points in the input.
• Notice that the closestPairs methods are static. That means (1) they can't access instance variables, and (2) you don't need to instantiate a ClosestPairs object to use them. Any data that you want to share with helper methods should be passed as a parameter.

Grading

There are several tiers to this project. Your grade will be based on how many you complete. (Unlike previous homework, you can still receive a decent grade if certain parts of this assignment don't work.)

Rules

• You may work in teams of two. But your teammate must have completed the same set of homework as you. (For example, if you have completed Homework 6, you may only pair with someone who has also completed Homework 6.)
• Teammates must work together at all times. You may not "divide and conquer". You may not have one person write a bunch of code and then just explain it when it works.

Suggestions

• Look at the rubric above and focus on one set of points at a time. For example, just get the basic algorithm working before worrying about how to handle ties, or even considering the tolerance.
• Do closestPairsBruteForce first, then work on the divide and conquer version. This is especially important when working with ties and tolerance. It will be much easier to get the ties working in the divide and conquer algorithm after you first work out the bugs in the brute force version.
• Remember, Points in a PointPair must be returned in lexicographic order to pass the tests. However, until you return your final answer, it doesn't really matter what order the points are in.
• You will need your recursive divide and conquer calls to return both the closest pairs and the distances between those pairs. I did this by having my "helper" functions use set<pair<double, PointPair>> as a return value. (To avoid a lot of typing, I added this to the ClosestPairs: using PointPairDistSet = set<pair<double, PointPair>>;.
• The divide and conquer code is simipler if you can assume that each recursive call returns at least one pair of points (i.e., that the return set is not empty). One way to do this is to use a brute force search when your recursive call is down to the last 5 or so points. As mentioned above, you need not only the closest points, but the distances as well. I wrote a helper function for brute force that returns set<pair<double, PointPair>>. This helper function is used by both the main brute force function and my divide and conquer helper.

Submission and grading

• Please make sure your name appears in all source code files.
• Make sure all relevant code (including unit tests) is checked in to GitHub by the due date.
• Unless you indicate otherwise, I will assume that the code to be graded is on the master branch.

Updated Wednesday, 27 November 2019, 1:10 PM