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}-distanceDist_{\infty}^{(F,w)}(A,B) between an input sequence (resp. matrix)Aand the outputB. The distance is dependent on a familyFof intervals (resp. rectangular regions) for the sequence rounding (resp. matrix rounding) and positive-valued weight functionwon the family. We give efficient polynomial-time algorithms for the sequence-rounding problem for weightedl_{\infty}-distance with respect to any weight function w and any familyFof 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 unweightedl_{\infty}-distance associated with the familyWof all 2 x 2 square regions._{2}

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.