Friday, December 02, 2005

Geometric puzzle: division of k-d space using (k-1) dim objects

Given 2 points, how can you divide a a line so that you maximize the number of regions?

Given 3 lines, how can you divide the 2 dimensional space (a plane) so that you maximize the number of regions?

Given 4 planes, how can you divide the 3 dimensional space so that you maximize the number of regions?

Can you think of a way to divide a k-dimensional space by (k-1) dimensional objects, so you maximize the number of regions?



Solution: build a k-dimensional solution from a (k-1)-dimension solution.

No comments: