Induced well-distributed sets in Riemannian spaces

ABSTRACT

The concept of Riemannian geometries is used to construct induced homogeneous point sets on manifolds that are based on well-distributed point sets in unit cubes of an appropriately chosen Euclidean space. These well-distributed point sets in unit cubes are based on standard low-discrepancy sequences. The approach is algorithmic, that is, the methods developed in this article have been implemented and tested. Applications in image processing, graph theory and measurement-based exploration are presented.

REFERENCES

• 1: Corput, J. G. V. D. 1935. Nederl. Akad. Wetensch. Proc. Ser. B 38 813, 1058.
• 2: Alfred Gray, Modern Differential Geometry of Curves and Surfaces with Mathematica, CRC Press, Inc., Boca Raton, FL, 1996
• 3: Halton, J. H. 1960. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84--90.
• 4: Ladislav Kocis , William J. Whiten, Computational investigations of low-discrepancy sequences, ACM Transactions on Mathematical Software (TOMS), v.23 n.2, p.266-294, June 1997 [doi>10.1145/264029.264064]
• 5: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 6: Richtmyer, R. D. 1951. The evaluation of definite integrals and quasi-Monte Carlo method based on the properties of algebraic numbers. Report LA-1342, Los Alamos Scientific Laboratory, Los Alamos, NM.
• 7: Richtmyer, R.D. 1958. A non-random sampling method, based on congruences for Monte Carlo problems. Report NYO-867, New York, Institute of Mathematical Sciences, New York University.
• 8: Roweis, S. T. and Saul, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.
• 9: Sobol, I. M. 1967. On the distribution of points in a cube and the approximative evaluation of integrals. USSR Comput. Math. Mathemat. Phys. 7, 86--112.
• 10: Tenenbaum, J. B., de Silva, V., and Langford, J. C. 2000. A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2322.
• 11: Wenzel, L., Rajagopal, R., and Nair, D. 2001. Low-discrepancy curves and efficient sampling strategies. Manuscript.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms, Measurement, Theory

Keywords:
Riemannian geometry, image processing, low-discrepancy sequences, well-distributed point sets