Name
Abstract | ||
|---|---|---|
What is the least surface area of a shape that tiles $\R^d$ under translations by $\Z^d$? Any such shape must have volume~$1$ and hence surface area at least that of the volume-$1$ ball, namely $\Omega(\sqrt{d})$. Our main result is a construction with surface area $O(\sqrt{d})$, matching the lower bound up to a constant factor of $2\sqrt{2\pi/e} \approx 3$. The best previous tile known was only slightly better than the cube, having surface area on the order of $d$. We generalize this to give a construction that tiles $\R^d$ by translations of any full rank discrete lattice $\Lambda$ with surface area $2 \pi \fnorm{V^{-1}}$, where $V$ is the matrix of basis vectors of $\Lambda$, and $\fnorm{\cdot}$ denotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz~\cite{Raz08} in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in $\R^d$ to rectangular lattice points. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/FOCS.2008.50 | Philadelphia, PA |
Keywords | Field | DocType |
computational geometry,lattice theory,Frobenius norm,full rank discrete lattice,least surface area,lower bound,random tessellation process,rectangular lattice,rounding,shape surface area,spherical cubes,Foams,Parallel Repetition,Rounding,Tiling | Rank (linear algebra),Discrete mathematics,Combinatorics,Upper and lower bounds,Matrix (mathematics),Matrix norm,Rounding,Lattice (group),Tessellation,Mathematics,Cube | Conference |
ISSN | ISBN | Citations |
0272-5428 | 978-0-7695-3436-7 | 5 |
PageRank | References | Authors |
0.49 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kindler, G. | 1 | 5 | 0.49 |
| Ryan O'Donnell | 2 | 5 | 0.49 |
| Anup Rao | 3 | 581 | 32.80 |
| Avi Wigderson | 4 | 8205 | 1064.31 |