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

Jobst Heitzig heitzig-j at web.de
Tue Jun 3 12:57:57 PDT 2003

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
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.

More information about the Compgeom-announce mailing list