Conference rusure::math

        reply .0
    
    I came up with the barycenter of the points, however I can prove it only
in the case that the points are arrange symmetrically.  The problem is 
to minimize the mean distance as opposed to the mean squared distance to the 
N points. In the latter case, a direct computation with partial derivatives
show a solution at the barycenter of the points.

Do you have a configuration of points where the mean distance minimizer and
the mean squared distance minimizer are different?

    

    The N points are actually location of equipment at customer sites.
    I need an algoritm to compute the optimal position (minimum mean
    distance to equipment), for a FS office.
    
    Olav

>    The N points are actually location of equipment at customer sites.
>    I need an algoritm to compute the optimal position (minimum mean
>    distance to equipment), for a FS office.

Before I take a shot this, you should note that unless you
can fly straight to a customer site, this is not really a problem in
geometry, but one in graph theory.  Remember that you have to get to
the customer site by roads.  You might also want to build the FS office near a
road :-).  You might also want to think about weighting the sites by the amount
of equipment there, since you will probably be making more frequent trips
to those sites with more equipment (given the dubious assumption that
the reliability of all our equipment is the same) or those sites with
the least reliable equipment.

Having noted these, here's a cheap, dirty, and probably inaccurate
way to get a first shot at an appropriate site.

I assume that these sites are close enough that Euclidean plane geometry will
suffice. The earth's surface is not really flat, but over small areas, flatness
is a reasonable approximation, especially for lazy engineers like myself.

Express each of the site positions as an (x,y) vector from an arbitrarily
chosen reference position (a convenient choice of reference position is
probably one of the customer sites) and arbitrarily oriented orthogonal
axes.  Let V(n) = (x(n), y(n)).  Form:

		Sum( 1, n, V )/n

where Sum is the real sum from the first integer parameter to the second of the
real vector in the third.  This result is a vector to the mean position.
All the sites are weighted equally.

I'm not sure if this is the same as the point having the lowest mean
distance to any of the sites, but it seems plausible.  Does anyone have
a proof/disproof ?

The general solution is probably best found by relaxation methods, in any
case. The reality of city traffic patterns is such that 'taxicab' geometry may
be quite valuable... I don't think we are going to be able to find a solution
that is both realistic and mathematically interesting! 

    re: .6 - Peter, I yield to the reality of hard numbers, but now wonder
    where is the error in the mathematics.  After all, it should be
    nothing more than your work minus the square roots.  Of course,
    my calculus was over 20 years ago...
    
    Is there a reasonable worst-case error bound on the arithmetic mean?
    Assuming some maximum distance M between points, or total distance T,
    or some similar criterion.  If we want to provide a real-world answer,
    is the arithmetic mean good enough?  If not, how fast does iteration
    converge?
    
      John

    re .5
    
    A function is monotonic iff it is order preserving. It needs a domain
    that is ordered and a co-domain that is ordered.  A function defined
    on a region in an N-space is not monotone since the N-space is not
    ordered. I think that is the cause of the disonence between your
    result and the counter-example.
    
    

Consider the one-dimensional case.  The two proposed solutions yield
the mean and the median (or, if the number of points is even, any point
between the two center points).  The median gives the correct solution.

    Minimzing
    
    	      /	 N    2   \
    	sqrt (	Sum  Z     )
              \ i=1   i   /

    does not necessarily minimize
    
    		 N        /  2 \
    		Sum  sqrt(  Z   )
    		i=1       \  i /

    re priors
    
    Is there any physical process which is an analogue for this problem?
    
    I saw an article in Scientific American where a number of NP complete
    problems could be represented physically and "solved" in quick time.
    
    I will try to remember the year and the month of the issue and post
    it somewhere.
    
    

    Re .12:
    
    	I think I remember coming across that article too, but I can't
    remember what issue it was.
    
    	Solution in similiar line of that article may be as follows:
    
    	The N points are N fixed pins and the optimal point corresponds
    to a floating pin. Then somehow attach the floating pin with all
    the N fixed pins. Maybe by springs or rubber-bands. After the system
    goes into equilibrium, the position of the floating pin will be
    the optimal point.
    
    	However, this will yield a different answer from .5.
    In my case, the system will minimize the total potential energy
    which is kind of related to the square of the distance between 2
    points for a linear spring and not just the distance. Hence, the
    resulting solution actually minimizes the sum of the squares of
    the distances instead of just the sum of the distances.
    
    David Ng

    I agree with what .3 said. This is more of a problem in graph theory
    than in geometry.
    
    About whether this a NP-complete or not, I am not sure if you want
    to treat it as a graph theory problem. If the solution of .5 is
    what you want, that is definitely not a NP-complete problem since
    .5 is not a combinatorial algorithm and I think the word "NP-complete"
    only describes combinatorial problem. (??)
    
    David Ng
    
    

re .13
	If you use a table with holes in it and hang equal weights, ..., then
	this will yield the solution that minimizes the sum of the distances,
	since the potential energy of the system is minimized, and that implies
	that the lengths of the strings beneath the table is maximized.

    Actually, you can only be sure it is a local minimum,...
    
    /Bevin

    What is more, in even the simplest case of two points any point on
    the line segment between them meets the criteria.  With many points
    all sorts of things can happen.

    Off hand I don't know an easy way of obtaining the global minimum.

    - Jim