Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
D. T. Lee, C. K. Wong · SIAM Journal on Computing · 1980
In this paper we study the problem of scheduling the read/write head movement to handle a batch of $nI/O$ requests in a 2-dimensional secondary storage device in minimum time. Two models of storage systems are assumed in which the access time of a record (being proportional to the “distance” between the position of the record and that of the read/write head) is measured in terms of $L_1 $ and $L_\infty $ metrics, respectively. The scheduling problem, referred to as the Open Path Problem (OPP), is equivalent to finding a shortest Hamiltonian path with a specified end point in a complete graph with n vertices. We first show in this paper that there exists a natural isometry between the $L_1 $ and $L_\infty $ metrics. Consequently, the existence of a polynomial time algorithm for the OPP in one metric implies the existence of a polynomial time algorithm for the same problem in the other metric. Based on a result by Garey, Graham and Johnson, it is easy to show that the OPP in $L_1 $ (hence in $L_\infty $) metric is $NP$-complete. A heuristic to solve the OPP is therefore presented. It is based on a geometric structure called the Voronoi diagram in $L_1 $ metric. An optimal (worst-case) algorithm of time complexity $O(n\log n)$ for constructing the diagram for a set of n points in a plane is described. Using this diagram one can build a near-optimal path through each point either by constructing a minimum spanning tree or by the closest insertion method. Both algorithms are shown to take $O(n\log n)$ time which is the time for the construction of the diagram and yield an approximate solution within a factor of 2. The bound is also shown to be tight in the worse case. For the average case, simulation results show that the minimum spanning tree approach is better than the closest insertion method. As expected, they are far better than the sequential one in which the request is processed one at a time on the first-come–first-served basis.