Project #1

Given an array of 2D points (x,y coordinates), find the closest pair of points.

The distance between two 2D points can be calculated using the formula

from math import sqrt
dx = (x2 - x1)
dy = (y2 - y1)
dist = sqrt(dx**2 + dy**2)

Project #2

Given an array of 3D points (x,y,z coordinates), find the closest pair of points.

The distance between two 3D points can be calculated using the formula

from math import sqrt
dx = (x2 - x1)
dy = (y2 - y1)
dz = (z2 - z1)
dist = sqrt(dx**2 + dy**2 + dz**2)

Assuming Euclidean space, what about 4D, 5D, ...?

Requirement

Let the user chooses between using points in a file or points generated randomly.

Note: Predefined points in a file makes debugging easier. Tests can be repeated using the same input.

Things to think about

1. points only have integer coordinates
2. Limits on array size
3. coordinates limits
4. User interface,
   • Input file or random selection
   • Max array size
   • coordinate limits
5. Test/practice data
6. File format (csv, json, ...)

See the Python documentation for "random.randint"

FYI Links

Closest Pair of Points using Divide and Conquer algorithm