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.