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
SN - 0019-9958
VL - 63
SP - 39
EP - 57
JO - Information and Control
JF - Information and Control
IS - 1-2
ER -