טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMerksamer Yael
SubjectTwo Dimensional Cluster Error-Correcting Codes
DepartmentDepartment of Computer Science
Supervisor Professor Tuvi Etzion


Abstract

We consider various coloring problems of the points of .


It is known that at least colors ( colors) are required to color the points of , such that the -distance between any two points, colored with the same color, is at least (at least ). In this work we characterize all the colorings which attain these bounds.


We consider the problem of coloring the points of , such for any two points colored with the same color, whose -distance is smaller than , the -distance between them is at least . We give lower bounds on the number of colors required and show colorings which attain these bounds.


For , the tristance is a generalization of the -distance on to a quality that reflects the relative dispersion of three points rather than two. In this work we prove that at least colors are required to color the points of , such that the tristance between any three distinct points, colored with the same color, is at least . We prove that colors are required if the tristance is at least . For the first case we show an infinite family of colorings with colors and conjecture that these are the only colorings with colors.


These problems have applications in two-dimensional cluster error-correcting codes. They also have combinatorial interest, as the coloring structures obtained are generalizations of perfect codes of in the -metric and tiling of with Lee spheres.