TY - JOUR
T1 - A generalization of magic squares with applications to digital halftoning
AU - Aronov, Boris
AU - Asano, Tetsuo
AU - Kikuchi, Yosuke
AU - Nandy, Subhas C.
AU - Sasahara, Shinji
AU - Uno, Takeaki
N1 - Funding Information:
★★ Work of T.A. was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B).
Funding Information:
★ Part of the work on the paper has been carried out when B.A. was visiting JAIST. Work of B.A. on this paper was supported in part by NSF ITR Grant CCR-00-81964.
PY - 2004
Y1 - 2004
N2 - A semimagic square of order n is an n × n matrix containing the integers 0,... ,n2 -1 arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero k × k-discrepancy matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each k × k square contiguous submatrix be the same. We show that such matrices exist if k and n are both even, and do not if k and n are are relatively prime. Further, the existence is also guaranteed whenever n = km, for some integers k,m ≥ 2. We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned.
AB - A semimagic square of order n is an n × n matrix containing the integers 0,... ,n2 -1 arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero k × k-discrepancy matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each k × k square contiguous submatrix be the same. We show that such matrices exist if k and n are both even, and do not if k and n are are relatively prime. Further, the existence is also guaranteed whenever n = km, for some integers k,m ≥ 2. We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned.
UR - http://www.scopus.com/inward/record.url?scp=35048813548&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048813548&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-30551-4_10
DO - 10.1007/978-3-540-30551-4_10
M3 - Article
AN - SCOPUS:35048813548
SN - 0302-9743
VL - 3341
SP - 89
EP - 100
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -