I presume everyone is familiar with the problem of finding a median of a set of numbers (a median of a set is an element of the set so that at most half of the elements of the set are smaller than the median, and at most half of the elements are larger than the median. For instance, of the set 1, 2, 3, 4, 5, 6, the number 3 is a median (and so is 4)). A simple algorithm sorts the set of numbers, and then takes the middle element of the sorted list. But this takes Ω(N log N) worst case, as it needs to sort.

Warm-up problem: write a subroutine that takes a set of numbers (without implied order, and possible duplicates) and returns a median. The sub should run in O(N) time.

Generalizing this to 2-dimensions is easy - to find a line that separates a set of points in 2-d into two subsets each at most half the size of the original set. You'd just ignore the y-coordinate, find the median of the x-coordinates, and pick a line that has this x-coordinate a constant.

But it's more interesting if you have two sets of points: a set of red coloured points, and a set of green coloured points (both in 2-d). Now, there is a line (or more than one) that simultaneously divides the set of red points and the set of green points such that on the left of the line you have at most half of the red points and half of the green points, and on the right of the line, you have at most half of the red points, and at most half of the green points. (This means that if there are an odd number of red points and an odd number of green points to start with, the dividing line will contain at least one red, and at least one green point).

Challenge 1a: Write a subroutine that accepts two sets of points (in 2-d), and returns a line simultaneously dividing the sets as described above.
Challenge 1b: Can you do it in O(N log N) time, where N is the total number of points in both sets?
Challenge 1c: Can you do it in linear time, or prove it to be impossible?

Now, what holds of 2-d, holds for 3-d (and higher dimensions as well). Given sets of red, green and yellow points, there exists a plane that divides the three sets such that at most half of the red, green and yellow points are above the plane, and at most half of each set is below the plane. (This even holds for sets with an infinite amount of points, leading to the 'ham-cheese sandwich theorem' that states you can cut a ham-cheese sandwich into two parts with a single cut such that both halves at equal amounts of ham, cheese and bread - even if you leave the cheese in the fridge).

Challenge 2a: Write a subroutine that takes three sets of points in 3-d, return a plane dividing all the sets as described above.
Challenge 2b: Prove that your solution is optimal.

Challenge 3: Generalize the sub to do the same in any dimension.

Have fun!