  For an arbitrary given span of high-dimensional multivariate Chebyshev
polynomials, an approach to construct spatial discretizations is presented,
i.e., the construction of a sampling set that allows for the unique
reconstruction of each polynomial of this span.
  The approach presented here combines three different types of efficiency.
First, the construction of the spatial discretization should be efficient with
respect to the dimension of the span of the Chebyshev polynomials. Second, the
number of sampling nodes within the constructed discretizations should be
efficient, i.e., the oversampling factors should be reasonable. Third, there
should be an efficient method for the unique reconstruction of a polynomial
from given sampling values at the sampling nodes of the discretization.
  The first two mentioned types of efficiency are also present in constructions
based on random sampling nodes, but the lack of structure here causes the
inefficiency of the reconstruction method. Our approach uses a combination of
cosine transformed rank-1 lattices whose structure allows for applications of
univariate fast Fourier transforms for the reconstruction algorithm and is thus
a priori efficiently realizable.
  Besides the theoretical estimates of numbers of sampling nodes and failure
probabilities due to a random draw of the used lattices, we present several
improvements of the basic design approach that significantly increases its
practical applicability. Numerical tests, which discretize spans of
multivariate Chebyshev polynomials depending on up to more than 50 spatial
variables, corroborate the theoretical results and the significance of the
improvements.
