Programming Assignment #3

> > > > Programming Assignments > Assignment #3 - Closest Pair

Objectives

to implement a list ADT
to use lists
to implement algorithms efficiently

Introduction

CLOSEST-PAIR is the problem of, given a set of distinct points in the 2-D plane, finding the pair of points that is closest together. The straightforward algorithm for finding the closest pair would compute the distance for each pair of points and keep track of the minimum distance. If there are $n$ points in the input then there are ${n \cdot (n-1) \over 2}$ pairs of points to consider, so the straightforward algorithm runs in $\Theta(n^2)$ time.

There is a more efficient divide-and-conquer algorithm to determine the closest pair. This algorithm begins with a preprocessing step that creates two lists of the points, one sorted by x-coordinate and one sorted by y-coordinate. The recursive divide-and-conquer function then takes those two lists and

splits the points into the left half and right half, with each half stored again in two lists: one sorted by x-coordinate and one sorted by y-coordinate
recursively finds the closest pair of points in the left half and in the right half and determines which of those pairs is closer together (call the corresponding distance $d$)
creates a list of points in the middle vertical strip – less then $d$ horizontally from a vertical line that divides the left half from the right half
checks whether the closest pair of points in that middle strip is closer than $d$ apart.

As long as the initial sort is done in $O(n \log n)$ time and each step in the recursive function takes $O(n)$ time then the running time of the divide-and-conquer algorithm is $O(n \log n)$ overall.

Assignment

Write a program called ClosestPair that implements the $O(n \log n)$ divide-and-conquer algorithm for CLOSEST-PAIR. To facilitate writing your program, you must also implement an array-based ListOfPoints ADT as defined by the provided header file.

Your program should read the points from standard input and write the result to standard output. The first line of input will be an integer giving the number of points; there will be at least two points. The following lines of input will contain the coordinates of the points, with one point per line and with each line containing the x-coordinate of a point followed by the y-coordinate, separated by whitespace (and with possibly leading and trailing whitespace on each line); all the points will be distinct. Each coordinate will be a decimal floating-point value suitable for parsing by atof with no extra characters that would prevent atof from examining the entire input.

The output of your program should be of the form

(9.000000, 12.000000)-(10.000000, 11.000000)=1.414214

where each coordinate and the distance is output in the default form for printf and the first point listed is the one with the lower x-coordinate (lower y-coordinate if the x-coordinates are the same). If there are multiple pairs of points with the same distance then the one output should be the first one when all such pairs are sorted in increasing order by first x-coordinate, then first y-coordinate, then second x-coordinate, then second y-coordinate.

If the input is not as specified then your program must behave gracefully – it must not crash or go into an infinite loop.

Your ListOfPoints ADT must work with the provided point header and implementation files and must be implemented in a file called plist.c. The provided point.h, point.c, and plist.h (don't change them but please submit them) and your plist.c must be the only files needed to use your ListOfPoints ADT, so that the command

    gcc -std=c99 -Wall -pedantic plist_unit.c plist.c point.c -lm

compiles with no warnings or errors (a sample plist_unit.c will be provided as part of the public tests).

Your program and any program that uses your ListOfPoints ADT correctly must not produce any error messages when run with valgrind --tool=memcheck --leak-check=yes -q.

We reserve the right to deduct points from submissions for violations of the following guidelines.

All source code should be easily comprehended, with adequate and consistent spacing, concise but descriptive idenitifiers, comments before long sequences of code, and enumerations and constants favored over literals.
Submissions should be modularized, with collections of related functions divided into separate files.
Each function should be documented with a comment before its declaration. The comment should include 1) a description of the parameters including any limitations on the values allowed (preconditions), and 2) a description of what the function does and/or what it returns (postconditions).
Header files should be written so that they can be #included regardless of what other files have been #included -- if a declaration is required by your header files, then #include the appropriate header file in your header file (or write a forward declaration in your header) rather than relying on your #includers to have already #included those header files before they #include yours.
Things that make sense to be declared as const should be declared as const.
There should be no warnings when your code is compiled with the -Wall and -pedantic options.

Example

If the input is

then the first level of the recursion splits the points into

x_left=[(2, 3), (2, 16), (3, 9), (6, 3), (7, 7), (9, 12)]
x_right=[(10, 11), (15, 2), (15, 19), (16, 11), (17, 13), (19, 4)]
y_left=[(2, 3), (6, 3), (7, 7), (3, 9), (9, 12), (2, 16)]
y_right=[(15, 2), (19, 4), (10, 11), (16, 11), (17, 13), (15, 19)]

The recursion on the left points splits them into

x_left=[(2, 3), (2, 16), (3, 9)]
x_right=[(6, 3), (7, 7), (9, 12)]
y_left=[(2, 3), (3, 9), (2, 16)]
y_right=[(6, 3), (7, 7), (9, 12)]

where the closest pair among the left/left points is (2,3)-(3,9) and the closest pair among the right/left points is (6,3)-(7,7), which is closer. Using $x=4.5$ as the dividing line, the middle strip is the points with x-coordinates between $4.5 \pm \sqrt{17}$: [(2, 3), (6, 3), (7, 7), (3, 9), (2, 16)]. The middle strip has no pair of points closer together than (6,3)-(7,7), so that is returned as the closest pair on the left.

The recursion on the right points splits them into

x_left:[(10, 11), (15, 2), (15, 19)]
x_right:[(16, 11), (17, 13), (19, 4)]
y_left:[(15, 2), (10, 11), (15, 19)]
y_right:[(19, 4), (16, 11), (17, 13)]

where the closest pair among the left/right points is (10,11)-(15,2) and the closest pair among the right/right points is (16,11)-(17,13), which is closer. Using $x=15.5$ as the dividing line, the middle strip is the points with x-coordinates between $15.5 \pm \sqrt{5}$: [(15, 2), (16, 11), (17, 13), (15, 19)]. The middle strip contains no pair of points closer together than (16,11)-(17,3), so that pair is returned as the closest pair on the right.

The initial call has now received (6,3)-(7,7) as the closest pair on the left and (16,11)-(17,13) as the closest pair on the right. (16,11)-(17,13) is the closer together of those two pairs. Using $x=9.5$ as the dividing line, the middle strip is the points with x-coordinates between $9.5 \pm \sqrt{5}$: [(10, 11), (9, 12)]. The middle strip contains the pair (9,12)-(10,11), which is closer together than (16,11)-(17,13) and is the closest pair out of all the original points.

Files

Files are available in /home/httpd/html/zoo/classes/cs223/f2017/Assignments/ClosestPair: