Computing rectangle enclosures |
| |
Authors: | V Bistiolas D Sofotassios A Tsakalidis |
| |
Institution: | Computer Technology Institute, P.O. box 1122, 261 10 Patras, Greece |
| |
Abstract: | The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log2 n) space. For the static case, the query time is O(log2 n log log n + K). The dynamic case is supported in O(log3 n + K) query time using O(log3 n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log2d-2 n log log n + K) for the static case and O(log2d-1 n + K) for the dynamic case. The space used is O(n> log2d-2 n) and the amortized time for an update is O(log2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log2d n + K) query time, O(log2d n) time for an insertion and O(log2d-1 n) time for a deletion. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|