Post office Problem

Discussion in 'Computer science & Electrical Engineering' started by gioxoaychieu, Aug 7, 2008.

  1. gioxoaychieu

    gioxoaychieu Thèm thuồng

    Ông thầy em lại hỏi em một bài toán khác.
    Let S be a set of n points in the plane. Given a query point q, we want to find a point in S that is closest to q. This problem is called a postoffice problem. For this problem consider the following scheme: Given n points, we first find a smallest square that contains all the points and decompose it into square root of n by square root of n cells (small squares). Then, as a preprocessing, for each cell C(i,j) we compute a set of points in S that fall in the cell. Then, given a query point q, we first find a cell that contains q and examine all the points in the cell to report which point is closest.
    1) Is this algorithm correct? Prove or disprove by a counter example.
    2) What is the running time of the algorithm in the worst case?
    (3) What is the best known algorithm for this problem?
    Bài toán này ðýợc ðýa ra và gọi tên post office problem trong quyển The Art of Computer Programming.
    (3) thì có thể trả lời ðýợc nhýng chýa chắc chắn, vì biết ðây có better algorithm. Nhýng (1) và (2) thuật toán lạ hoắc.
    Các bác có kiến thức về lĩnh vực này giúp em với ?
     
  2. DAK

    DAK Thèm thuồng

    Giải thuật láng giềng gần (Nearest neighbor search) chứ có gì xa lạ đâu.
    Vừa Google thử thì tất cả đều có hết trên wikipedia rồi, chịu khó lên đấy đọc:
    http://en.wikipedia.org/wiki/Nearest_neighbor_search
     

Share This Page