BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Pliska Studia Mathematica Bulgarica >
1998 Volume 12 >

Please use this identifier to cite or link to this item:

Title: A Fast Algorithm for Weber Problem on a Grid
Authors: Lee, H.
Keywords: Continued Fraction Expansions
Integer Programming
Location Problem
Number 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.
ISSN: 0204-9805
Appears in Collections:1998 Volume 12

Files in This Item:

File Description SizeFormat
Pliska-12-1998-057-070.pdf1.15 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License