とりあえず

shiroさんからもメッセージをいただいたことだし、何らかのWebの肥やしにはなるかもしれないので、擬似コードをもって昨日の一つ目の解決案を書こうと思います。
ちなみにこの手法は、「同一の領域に対して、複数(多数)の点からの距離を求めたい場合」にのみ有効であって、その他の場合には使い物になりません。一回距離を求める度に領域がどんどんと変化する場合は、逆に遅くなります。

class Search{
  List omega;
  public Search(int width, int height){
    this.width = width;
    this.height = height;
    omega = new LinkedList();
    initOmega();
  }
  private void initOmega(){
    for(int i = 0; i < this.width; i++){
      for(int j = 0; j < this.height; j++){
        if(isHoge(i, j) && 
             (!isHoge(i+1,j) || !isHoge(i-1,j) ||
              !isHoge(i,j+1) || !isHoge(i,j-1)))
          this.omega.add(new Point(i,j));
      }
  }
  public Point search(int x, int y){
    int length = this.width * this.width + this.height * this.height;
    Point tmp = null;
    for(Point p: this.omega){
      int l = (p.x-x)*(p.x-x) + (p.y-y)*(p.y-y);
      if(l < length){
        length = l;
        tmp = p;
      }
    }
    return tmp;
  }
  
}