Summary: Certain structure detection problems can be solved by sampling a parameter space for the different structures at a finite number of points and checking each point to see if the corresponding structure has a sufficient number of inlying measurements. The measurement space is a Riemannian manifold and the measurements relevant to a given structure are near to or on a submanifold which constitutes the structure. The probability density function for the errors in the measurements is described using a generalisation of the Gaussian density to Riemannian manifolds. The conditional probability density function for the measurements yields the Fisher information which defines a metric, known as the Fisher-Rao metric, on the parameter space. The main result is a derivation of an asymptotic approximation to the Fisher-Rao metric, under the assumption that the measurement noise is small. Using this approximation to the Fisher-Rao metric, the parameter space is sampled, such that each point of the parameter space is near to at least one sample point, to within the level of accuracy allowed by the measurement errors. The probability of a false detection of a structure is estimated. The feasibility of this approach to structure detection is tested experimentally using the example of line detection in digital images.