請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38473
標題: Finding Intersection of Rectangles by Range Search
作者: D.T.Lee
C.K.Wong
摘要: Three related rectangle intersection problems in k-dimensional space are considered: (1) find the intersections of a rectangle with a given set of rectangles, (2) find the intersecting pairs of rectangles as they are inserted into or deleted from an existing set of rectangles, and (3) find the intersecting pairs of a given set of rectangles. By transforming these problems into range search problems, one need not divide the intersection problem into two subproblems, namely, the edge-intersecting problem and the containment problem, as done by many previous studies. Furthermore, this approach can also solve these subproblems separately, if required. For the first problem the running time is O((log n)2k−1 + s), where s is the number of intersecting pairs of rectangles. For the second problem the time needed to generate and maintain n rectangles is O(n(log n)2k) and the time for each query is O((log n)2k−1 + s). For the third problem the total time is O(n log n + n(log n)2(k−1) + s) for k ≥ 1.
URI: http://hdl.handle.net/11455/38473
顯示於類別:資訊科學與工程學系所

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


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