Geometric Retrieval Problems

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+e, lognlog(l/∈)) spacetime algorithm for the polygon retrieval problem, for arbitrarily small ∈, improving on the previous solution having complexity O(n7, logn).

Authors

• Richard Cole 0001
• Chee-Keng Yap

Keywords

• Data structures
• Runtime
• Costs
• Aerospace simulation
• Nearest neighbor searches
• Strontium
• Robustness
• Time measurement
• Data Structure
• Tetrahedral
• Space Complexity
• Space Requirements
• Query Time
• Tetragonal
• 3D Space
• Part Of The Solution
• Convex Hull
• Pair Of Points
• Basal Plane
• Email Lists
• Points In Order
• Storage Requirements
• Recursive Algorithm
• Subset Of Points
• Half Space
• Private Communication
• List Length
• Intercept Point
• Local Structure Of Data