REPORT breuel-93.04/IDIAP The 3D Indexing Problem Breuel, Thomas M. 3D model base indexing 3D object recognition algebraic varieties arrangements computational complexity computational geometry computer vision geometric hashing invariants point location algorithms view sets visual object recognition EXTERNAL http://publications.idiap.ch/attachments/reports/1993/93-08.pdf PUBLIC Idiap-RR-08-1993 1993 IDIAP This paper discusses the problem of 3D indexing. That is, given a collection of 3D object models (CAD models, formalized as collections of labeled 3D points,',','), an indexing algorithm may perform off-line pre-processing to generate a data structure that allows it to decide quickly whether a given 2D image was contains any of the objects represented by the 3D models. We first review and develop some mathematical machinery. Next, the indexing problem is related to well-known point-location and search problems in computational geometry. Based on such relationships, a number of asymptotically optimal indexing algorithms are discussed. We then observe that all algorithms related to this problem that have been developed in computer vision as well as in computational geometry show either suboptimal (near-linear) complexity in the number of 3D models, or require a super-polynomial amount of space to represent the result of the pre-computation. Such computational limitations are illustrated by a discussion of several commonly used approaches to 3D indexing (view-based indexing, indexing by invariants). We conclude with the speculation that, ultimately, the situation for 3D indexing algorithms is likely to remain analogous to that of high-dimensional geometric query problems: while asymptotically efficient algorithms are known even in high dimensions, most practical applications use linear time algorithms and are content with methods that give significant constant-factor speedups.