Yes, this quadtree/octree concept seems to be quite a fashionable idea in the game AI developers' world, but I side with Cheeseh, it might not be desirable to need that level of complexity to limit the number of waypoints to search from. Personally I use a 2D hashtable to store my walkfaces, like Cheeseh again. If I want to expand from a given [x][y] I look successively in [x-1][y-1], [x-1][y], [x-1][y+1], [x][y+1], [x+1][y+1], [x+1][y], [x+1][y-1], [x][y-1] (i.e. I circle around the slot) which in total leads me to only 9 slots to search into.
However Akz's explanation of the octree screams out for a wiki article ASAP