Search

For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the $$L_1$$ geodesic diameter in $$O(n^2+h^4)$$ time and the $$L_1$$ geodesic center in $$O((n^4+n^2 h^4)\alpha (n))$$ time, respectively, where $$\alpha (\cdot )$$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $$O(n^{7.73})$$ or $$O(n^7(h+\log n))$$ time, and compute the geodesic center in $$O(n^{11}\log n)$$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $$L_1$$ shortest paths in polygonal domains. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]