A fast algorithm for locating supplying center on a lattice

Abstract

One of the well known location problems 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. The solution domain considered here is confined to lattice 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 recursively.

Keywords:

• Continued fraction expansions
• integer programming
• location problem
• number theory

C.R. Categories:

• F2.2
• G2.1