標題: Voronoi Diagrams in L1 (L∞) Metrics with 2-Dimensional Storage Applications 作者: D.T.LeeC.K.Wong 出版社: Society for Industrial and Applied Mathematics 摘要: In this paper we study the problem of scheduling the read/write head movement to handle a batch of n UO 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 L1 and Lo 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 L1 and Loo 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 L1 (hence in L) 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 metric. An optimal (worst-case) algorithm of time complexity O(n log nkfor 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. URI: http://hdl.handle.net/11455/38488 ISSN: 0097-5397 顯示於類別： 資訊科學與工程學系所

Citations: