A Fast Algorithm for Weber Problem on a Grid

AMS subject classification: 90B80.

The Weber problem is to find a supply point in a plane such that total weighted distance between supply point and a set of demand points is minimized. No known algorithm finds the exact solution. In this paper, we consider a restricted case of Weber problem. The solution domain considered here is confined to grid points (that is, points with integer coordinates). Given m demand points in a plane and a convex polygon P with n vertices, we propose an algorithm to find a supply point with integer coordinates in convex polygon P such that total weighted distance from the point to these m points is minimized. If P is contained in U × U lattice, the worst case running time of the algorithm is O((n + m) log U + log2 U ). Our method works as follows. Fist, the searching domain polygon P is transformed so that either a number of horizontal grid lines can cover P or a central grid point in P can be found. If the first case holds, the supply point with integer coordinates can be found easily by scanning the grid points on those covering grid lines. Otherwise, we can prune a way a fixed fraction of the polygon by drawing a tangent line through the central grid point so that a smaller searching domain P can be obtained and do the searching recursively.

This research work was partially supported by the National Science Council of the Republic of China under grant No. NSC86-2416-h-019-001-