@inproceedings{ad3f7fb771464b24b5bf778409c34ba5,
title = "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 × 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.",
keywords = "Digital geometry, Discrete geometry, Star-shaped regions, Tree embedding",
author = "Jinhee Chun and Matias Korman and Martin N{\"o}llenburg and Takeshi Tokuyama",
year = "2008",
doi = "10.1145/1377676.1377737",
language = "English",
isbn = "9781605580715",
series = "Proceedings of the Annual Symposium on Computational Geometry",
pages = "355--364",
booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",
note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",
}