ORTHOGONAL QUERIES IN SEGMENTS

We consider the orthgonal clipping problem in a set of segments: Given a set of n segments in d-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segmen ts intersecting it can be counted/reported efficiently. We show that t he efficiency of the data structure significantly depends on a geometr ic discrete parameter K named the projected-image complexity which bec omes Theta (n(2)) in the worst case but practically much smaller. If w e use O (m) space, where K log(4d-7) n greater than or equal to m grea ter than or equal to n log(4d-7) n, the query time is O((K/m)(1/2) log (max{4,4d-5}) n). This is near to an Omega((K/m)(1/2)) lower bound.