Q: smallest n-cube containing k points in euclidean n-space?

[Jobst Heitzig <heitzig-j@web.de>]

Hello everybody!


Some problems:

Q1: Given k points in Euclidean n-space,
    what is the smallest n-cube containing all of them?

Probably equivalent question:

Q2: Given
	X = some k-dimensional metric space
	Y = n-th power of unit interval, with euclidean metric
    Can X be embedded isometrically into Y?

And finally my main problem:

Q3: Given
	M = some k-dimensional correlation matrix
	    (i.e. positive semi-definite, all entries in [-1,1],
	     unit diagonal)
	Y = n-th power of interval [-b,b] for some positive b
    Are there k vectors x_1,...,x_k in Y such that
    M_ij is the scalar product of x_i and x_j for all i,j?

(In other words: When can we realize a correlation matrix of k variables 
 with n observations, where the variables satisfy some given bounds?)


Jobst Heitzig,
Statistisches Bundesamt Deutschland


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request@research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.