I second kd-trees. I also only recently learned them, and at first encounter thought that they are in concept similar to binary space partitions used in computer graphics. Nearest neighbor search can be implemented using a pretty simple two-dimensional kd-tree. Useful for things like finding the n closest neighboring points for a given point on a plane (used for mapping applications, etc.)