TY - JOUR

T1 - Geometric retrieval problems

AU - Cole, Richard

AU - Yap, Chee K.

N1 - Funding Information:
* This is substantially the same as the "Proc. IEEE Annu. Found. Comput. Sci.," 1983 paper by the same title except for some minor improvements and the removal of the circular retrieval results which are being prepared for separate publication. This work has been supported by grants from the Digital Equipment Corporation, The Sloan Foundation, the System Development Foundation, the IBM corporation, and ONR Grant N00014-82-K-0381. It is also supported by NSF Grant DCR-84-01633 and by an IBM Faculty Development Award.

PY - 1984

Y1 - 1984

N2 - A large class of geometric retrieval problems has the following form. Given a set X of geometric objects, preprocess to obtain a data structure D(X). Now use D(X) to rapidly answer queries on X. We say an algorithm for such a problem has (worst-case) space-time complexity O(f(n), g(n)) if the space requirement for D(X) is O(f) and the "locate run-time" required for each retrieval is O(g). We show three techniques which can consistently be exploited in solving such problems. For instance, using our techniques, we obtain an O(n2 + ε/log n, log n log(1/ε)) space-time algorithm for the polygon retrieval problem, for arbitrarily small ε, improving on the previous solution having complexity O(n7, log n).

AB - A large class of geometric retrieval problems has the following form. Given a set X of geometric objects, preprocess to obtain a data structure D(X). Now use D(X) to rapidly answer queries on X. We say an algorithm for such a problem has (worst-case) space-time complexity O(f(n), g(n)) if the space requirement for D(X) is O(f) and the "locate run-time" required for each retrieval is O(g). We show three techniques which can consistently be exploited in solving such problems. For instance, using our techniques, we obtain an O(n2 + ε/log n, log n log(1/ε)) space-time algorithm for the polygon retrieval problem, for arbitrarily small ε, improving on the previous solution having complexity O(n7, log n).

UR - http://www.scopus.com/inward/record.url?scp=0021503111&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021503111&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(84)80040-6

DO - 10.1016/S0019-9958(84)80040-6

M3 - Article

AN - SCOPUS:0021503111

VL - 63

SP - 39

EP - 57

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 1-2

ER -