MySQL supports spatial indexes exactly for circumstances like this:

http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.ht...