How to find the spot which is furthest away? Last night I thought about the following problem:
 
Given any map (for example from Germany), how to find the spot which is furthest away (in every direction) from the nearest (any) town/village?
 
I thought about how one would proceed to figure out in which problem class this problem belongs to and how to prove that. 
And also how to determine which would be an efficient algorithm for this problem.  
Basically I would like to learn about the steps how a professional in complexity theory would start to work on a problem like this.
 
I read on Wikipedia about the Nearest neighbor search which I think come close to what I'm looking for. But I wasn't able to find something like "furthest neighbor search".
As you get further from Germany, you will get points which are farther and farther away. So unless you are taking into account the spherical nature of Earth, we need to change the problem, and look for a location in Germany which is farthest away from all villages in Germany. This is known as the largest empty circle problem, and can be solved essentially by computing the Voronoi diagram of the set of villages in Germany.