DocumentCode :
2993303
Title :
On the number of digital straight lines on an N×N grid
Author :
Lindenbaum, M. ; Koplowitz, J. ; Bruckstein, A.
Author_Institution :
Dept. of Electr. Eng., Technion, Israel Inst. of Technol., Haifa, Israel
fYear :
1988
fDate :
5-9 Jun 1988
Firstpage :
610
Lastpage :
615
Abstract :
The number of different digital straight lines on an N×N square pixel array is studied. The problem is equivalent to finding the number of linear dichotomies of a planar set of N2 points of an N×N grid. For any planar set of points, adjacent pairs are defined to be pairs of points from the set such that no other point from the set lie on the line segment between them. A one-to-one correspondence between linear dichotomies and adjacent pairs is proved. Then, the adjacent pairs of points of an N×N grid are counted, and the number of linear dichotomies, as well as the number of digital straight lines, follows. An asymptotic evaluation is proved and an efficient algorithm for finding L(N) for any particular N is given
Keywords :
computational geometry; computerised picture processing; adjacent pairs; computerised picture processing; digital straight lines; geometry; line segment; linear dichotomies; pixel array; Joining IEEE; Pattern recognition; Pixel;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision and Pattern Recognition, 1988. Proceedings CVPR '88., Computer Society Conference on
Conference_Location :
Ann Arbor, MI
ISSN :
1063-6919
Print_ISBN :
0-8186-0862-5
Type :
conf
DOI :
10.1109/CVPR.1988.196299
Filename :
196299
Link To Document :
بازگشت