M.Sc Thesis | |
M.Sc Student | Merksamer Yael |
---|---|
Subject | Two Dimensional Cluster Error-Correcting Codes |
Department | Department of Computer Science | Supervisor | PROF. Tuvi Etzion |
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.