Consistent digital rays

ABSTRACT

Given a fixed origin o in the d-dimensional grid, we give a novel definition of digital rays dig(op) from o to each grid point p. Each digital ray dig(op) approximates the Euclidean line segment op between o and p. The set of all digital rays satisfies a set of axioms analogous to the Euclidean axioms. We measure the approximation quality by the maximum Hausdorff distance between a digital ray and its Euclidean counterpart and establish an asymptotically tight Θ(log n) bound in the n x n grid. The proof of the bound is based on discrepancy theory and a simple construction algorithm. Without a monotonicity property for digital rays the bound is improved to O(1). Digital rays enable us to define the family of digital star-shaped regions centered at o which we use to design efficient algorithms for image processing problems.

REFERENCES

• 1: T. Asano, D. Z. Chen, N. Katoh, and T. Tokuyama. Efficient algorithms for optimization-based image segmentation. Internat. J. Comput. Geom. Appl., 11(2):145--166, 2001.
• 2: Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
• 3: D. Z. Chen, J. Chun, N. Katoh, and T. Tokuyama. Efficient algorithms for approximating a multi-dimensional voxel terrain by a unimodal terrain. In Proc. 10th Ann. Int. Conf. Computing and Combinatorics (COCOON'04), volume 3106 of Lecture Notes in Comput. Sci., pages 238--248. Springer Verlag, 2004.
• 4: J. Chun, K. Sadakane, and T. Tokuyama. Efficient algorithms for constructing a pyramid from a terrain. In Proc. Japanese Conf. on Discrete and Computational Geometry (JCDCG'02), volume 2866 of Lecture Notes in Comput. Sci., pages 108--117. Springer Verlag, 2003.
• 5: P. Erdös. Problems and results on diophantine approximation. Compos. Math., 16:52--65, 1964.
• 6: J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73046]
• 7: Michael T. Goodrich , Leonidas J. Guibas , John Hershberger , Paul J. Tanenbaum, Snap rounding line segments efficiently in two and three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.284-293, June 04-06, 1997, Nice, France [doi>10.1145/262839.262985]
• 8: Daniel H. Greene , F. Frances Yao, Finite-resolution computational geometry, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.143-152, October 27-29, 1986 [doi>10.1109/SFCS.1986.19]
• 9: Reinhard Klette , Azriel Rosenfeld, Digital straightness: a review, Discrete Applied Mathematics, v.139 n.1-3, p.197-230, 30 April 2004 [doi>10.1016/j.dam.2002.12.001]
• 10: J. Matousêk. Geometric Discrepancy: An Illustrated Guide. Springer Verlag, 1999.
• 11: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 12: J. Pach, R. Pollack, and J. Spencer. Graph distance and Euclidean distance on the grid. In R. Bodendiek and R. Henn, editors, Topics in Graph Theory and Combinatorics, pages 555--559. Physica-Verlag, 1990.
• 13: W. M. Schmidt. Irregularities of distribution, VII. Acta Arithmetica, 21:45--50, 1972.
• 14: W. M. Schmidt. Lectures on Irregularities of Distribution. Tata Inst. Fund. Res. Bombay, 1977.
• 15: Otfried Schwarzkopf, The extensible drawing editor Ipe, Proceedings of the eleventh annual symposium on Computational geometry, p.410-411, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220326]
• 16: Kokichi Sugihara, Robust Geometric Computation Based on Topological Consistency, Proceedings of the International Conference on Computational Sciences-Part I, p.12-26, May 28-30, 2001
• 17: J. van der Corput. Verteilungsfunktionen I & II. Nederl. Akad. Wetensch. Proc., 38:813-820, 1058--1066, 1935.
• 18: X. Wu. Efficient algorithms for the optimal-ratio region detection problems in discrete geometry with applications. In Proc. 17th Int. Symp. on Algorithms and Computation (ISAAC'06), volume 4288 of Lecture Notes in Comput. Sci., pages 289--299. Springer Verlag, 2006.
• 19: Xiaodong Wu , Danny Z. Chen, Optimal Net Surface Problems with Applications, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.1029-1042, July 08-13, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Theory

Keywords:
digital geometry, discrete geometry, star-shaped regions, tree embedding