Abstract | ||
---|---|---|
Given $k$ labelings of a finite $d$-dimensional cubical grid, define the combined distance between two labels to be the sum of the $\ell_1$-distance between the two labels in each labeling. We want to construct $k$ labelings which maximize the minimum combined distance between any two labels. When $d=1$, this can be interpreted as placing $n$ nonattacking rooks in a $k$-dimensional chessboard of size $n$ in such a way to maximize the minimum $\ell_1$-distance between any two rooks. Rook placements are also known as Latin hypercube designs in the literature. In this paper, we revisit this problem with a more geometric approach. Instead of providing explicit but complicated formulas, we construct rook placements in a $k$-dimensional chessboard of size $n$ as certain lattice-like structures for certain well-chosen values of $n$. Then, we extend these constructions to any values of $n$ using geometric arguments. With this method, we present a clean and geometric description of the known optimal rook placements in the two-dimensional square grid. Furthermore, we provide asymptotically optimal constructions of $k$ labelings of $d$-dimensional cubical grids which maximize the minimum combined distance. Finally, we discuss the extension of this problem to labelings of an arbitrary graph. We prove that deciding whether a graph has two labelings with combined distance at least $3$ is at least as hard as graph isomorphism. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1137/100815281 | SIAM Journal on Discrete Mathematics |
Keywords | DocType | Volume |
dispersion problem,graph isomorphism,geometric argument,dimensional cubical grid,combined distance,geometric approach,geometric description,arbitrary graph,rook placement,dimensional chessboard,minimum combined distance | Conference | 26 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Minghui Jiang | 1 | 498 | 54.84 |
Vincent Pilaud | 2 | 57 | 10.15 |
Pedro J. Tejada | 3 | 6 | 2.11 |