Consistent digital rays

Jinhee Chun, Matias Korman, Martin Nöllenburg, Takeshi Tokuyama

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)


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 × 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.

Original languageEnglish
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Number of pages10
Publication statusPublished - 2008
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: 2008 Jun 92008 Jun 11

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Conference24th Annual Symposium on Computational Geometry, SCG'08
Country/TerritoryUnited States
CityCollege Park, MD


  • Digital geometry
  • Discrete geometry
  • Star-shaped regions
  • Tree embedding


Dive into the research topics of 'Consistent digital rays'. Together they form a unique fingerprint.

Cite this