請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38488
標題: Voronoi Diagrams in L1 (L∞) Metrics with 2-Dimensional Storage Applications
作者: D.T.Lee
C.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
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。