ML Anthology

On the Number of Digital Straight Lines on an N×N Grid

Michael Lindenbaum, Jack Koplowitz, Alfred M. Bruckstein
CVPR 1988 pp. 610-615
doi:10.1109/CVPR.1988.196299 /cvpr/1988/lindenbaum1988cvpr-number/

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 N/sup 2/ 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

CVPR Semantic Scholar

Cite

Text

Lindenbaum et al. "On the Number of Digital Straight Lines on an N×N Grid." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988. doi:10.1109/CVPR.1988.196299

Markdown

[Lindenbaum et al. "On the Number of Digital Straight Lines on an N×N Grid." IEEE/CVF Conference on Computer Vision and Pattern Recognition, 1988.](https://mlanthology.org/cvpr/1988/lindenbaum1988cvpr-number/) doi:10.1109/CVPR.1988.196299

BibTeX

@inproceedings{lindenbaum1988cvpr-number,
  title     = {{On the Number of Digital Straight Lines on an N×N Grid}},
  author    = {Lindenbaum, Michael and Koplowitz, Jack and Bruckstein, Alfred M.},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year      = {1988},
  pages     = {610-615},
  doi       = {10.1109/CVPR.1988.196299},
  url       = {https://mlanthology.org/cvpr/1988/lindenbaum1988cvpr-number/}
}