Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a small set of points in $\mathbb{R}^3$ (around 4 to 10 points, say). I would like to project these points onto a 2D subspace such as to minimize the maximum change in Euclidean distances.

Formally, if $\{s_i\}_{i=1}^n$ are the points in $\mathbb{R}^3$ and $\rho$ denotes an arbitrary projection of these points onto a 2D subspace, then the minimum maximum change is $$\min_\rho \max_{1 \leq i<j \leq n} \big|\mathrm{dist}\big(s_i,s_j\big)-\mathrm{dist}\big(\rho(s_i),\rho(s_j)\big)\big|.$$

Question: How can we find a projection $\rho$ that achieves this value?

If we have at most $3$ points, we can project them onto a 2D subspace without any change in the Euclidean distances. If we have 4 or more points, we cannot in general, but we might be able to achieve something that's not too bad.

(Motivation: This is a problem that's come up in my research, but has taken me out of my field of expertise. It's related to graph drawing. In particular, I'm attempting to draw graphs in 2D which are defined geometrically in 3D.)

share|improve this question
    
This looks like linear regression. You want to find the plane that approximates your points the best. Thus, set up the system of equations $ax_i+by_i+cz_i=d$ for all $s_i=(x_i,y_i,z_i)$ and solve it with the least squares method. It will probably not minimize your expression, but it seems close enough to what you want. –  Samuel Apr 22 '13 at 13:40
    
Or you can use nonlinear least squares if you know explicit equation of the plane... –  Occupy Gezi Apr 22 '13 at 13:41
    
The two comments above are offering you least-squares solutions, and you asked for a minimax solution. The two solutions are different, but least-squares is easier to compute. Do you really need a minimax solution? –  bubba Apr 22 '13 at 14:15
    
What I need is not set in stone (this is research-in-progress). In any case, I'd be interested in hearing about reasonable alternatives. Finding a plane of best fit seems like it's worth a shot (I'd have to try it out before I know though). –  Douglas S. Stones Apr 22 '13 at 14:19
    
The least-squares plane is straightforward -- see geometrictools.com/LibMathematics/Approximation/…, for example. –  bubba Apr 24 '13 at 2:48
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.