Consistent Digital Rays |
| |
Authors: | Jinhee Chun Matias Korman Martin Nöllenburg Takeshi Tokuyama |
| |
Institution: | (1) Graduate School of Information Sciences, Tohoku University, Sendai, Japan;(2) Faculty of Informatics, Karlsruhe University and Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany |
| |
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 \(\overline {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 |
本文献已被 SpringerLink 等数据库收录! |
|