Geometric retrieval problems

Research output: Contribution to journalArticle

Abstract

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).

Original languageEnglish (US)
Pages (from-to)39-57
Number of pages19
JournalInformation and Control
Volume63
Issue number1-2
DOIs
StatePublished - 1984

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Geometric retrieval problems'. Together they form a unique fingerprint.

  • Cite this