The 'Cross" Rectangle Intersection Problem
V. Kapelios, G. Panagopoulou, Georgios P. Papamichail, Spiros Sirmakessis, Athanasios Tsakalidis · The Computer Journal · 1995
In this paper we present a solution for a special case of the general rectangle intersection problem that has not been previously considered as a different case. This case, named the 'cross' intersection case, reports the set of these iso-oriented rectangles that intersect a query rectangle but do not enclose it and do not have one of their vertices inside it. We present solutions for unrestricted and restricted universe (grid) for the R d space. In the case of unrestricted d-dimensional space, the problem is solved in time O(log M ~ 3 nIoglogn + K) using O(/ilog M ~ 3 /i) space, where n is the number of rectangles and K is the size of the answer. In the case of restricted universe the same problem can be solved in O(\og d ~ 1 M+K) time and O{ity/\ogM ~ ) space, where M is the upper limit of the grid coordinates. Update operation in the dynamized version of the problem for the unrestricted and grid case is performed in 0(log 2< '~ 2 n) and O(\og d ~ i M) time, respectively.