Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/2124

 Title: A Fast Algorithm for Weber Problem on a Grid Authors: Lee, H. Keywords: Continued Fraction ExpansionsInteger ProgrammingLocation ProblemNumber Theory Issue Date: 1998 Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences Citation: Pliska Studia Mathematica Bulgarica, Vol. 12, No 1, (1998), 57p-70p Abstract: 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. Description: AMS subject classification: 90B80. URI: http://hdl.handle.net/10525/2124 ISSN: 0204-9805 Appears in Collections: 1998 Volume 12

Files in This Item:

File Description SizeFormat