AbstractIn this paper, we discuss the problem of computing an optimal rounding of a real sequence (resp. matrix) into an integral sequence (resp. matrix). Our criterion of the optimality is to minimize the weighted l_{\infty}-distance Dist_{\infty}(F,w)(A,B) between an input sequence (resp. matrix) A and the output B. The distance is dependent on a family F of intervals (resp. rectangular regions) for the sequence rounding (resp. matrix rounding) and positive-valued weight function w on the family. We give efficient polynomial-time algorithms for the sequence-rounding problem for weighted l_{\infty}-distance with respect to any weight function w and any family F of intervals. For the matrix-rounding problem, we prove that it is NP-hard to compute an approximate solution with approximation ratio smaller than 2 with respect to the unweighted l_{\infty}-distance associated with the family W2 of all 2 x 2 square regions.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; I.4 [Image Processing]
Additional Key Words and Phrases: algorithms, rounding, halftoning, sequence
Selected references
- Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan. Faster algorithms for the shortest path problem. Journal of the ACM, 37(2):213-223, April 1990.
- Tetsuo Asano, Danny Z. Chen, Naoki Katoh, and Takeshi Tokuyama. Polynomial-time solutions to image segmentation. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 104-113, Atlanta, Georgia, 28-30 January 1996.
- Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013-1036, October 1989.