3

So, I have a lot of points, and I need to site three new points so they will be at the shortest euclidean distance between all of the other points.

In other words, these three new points that I need to site will minimize the sum distance that the large group of points will be from any new point. I need to find the most efficient positioning the new points so the group of points will have the smallest total distance from a new point.

I'd like to be able to do this in Model Builder, or at least develop some kind of process that I can translate into Model Builder and possibly a python script later on (though I'm really bad at python). I assume this will involve some kind of iterative procedure, I just don't really know where to start.

Anyone have any awesome ideas?

P.S. This is in ArcGIS desktop 10.0

Edit: The idea is to site three new points that would be distributed to minimize total sum difference, thus they would, I guess, be taking a subset of the total point set to find the median center of them. It would look something like this (where the orange points would be something like the theoretical new locations):

Point Pattern

Edit 2: Okay, this has been confusing, but I was going on the description I was given for this particular problem. Yes, the minimized sum distance is the centroid. Mathematically, this is the best solution I've come up with so far, where the goal is the minimize Dist, but it just gets the total centroid: Math

I've now talked to a spatial statistics instructor at an Ivy league university and two Ph.D.'s in math and we still can't figure out an appropriate answer that satisfies what I've been asked.

The only other thing that I can think to do is to somehow evenly divide the original points into three spatially equal parts and find their centroids, but I don't know how to do that.

Improve this question
6
  • 1
    Are the three points meant to be for "all the points", or to "grab" some proportion of the points each, rather than being "shortest" for all of the points?
    – BradHards
    Commented Apr 15, 2013 at 4:35
  • 2
    Isn't this a location-allocation problem?
    – mkennedy
    Commented Apr 17, 2013 at 0:01
  • Yes, but not in a network analyst sense. Or it may be. I don't know, thanks for the vocabulary!
    – Wes
    Commented Apr 17, 2013 at 0:12
  • After you have the centroid, take the median/average distance to all the points from the centroid. Use that distance to create a circle and place the 3 points 2/3 pi apart. I'm probably wrong about this, but wherever you start the points on the circle -- the min sum difference of the combined 3 points would be the same -- it would just be essentially an exploded centroid. Worth a test?
    – awesomo
    Commented Apr 17, 2013 at 0:55
  • 2
    (1) No, the minimizing the sum of the distances does not give you the centroid. You need to square the distances. (2) I think you've got the problem posed in a squirrelly way. From your formula it looks like I should choose the 3 new points to be coincident.
    – cffk
    Commented Apr 17, 2013 at 1:05

2 Answers 2

Reset to default
1

If I am understanding your question correctly I think you can do this by calculating the median center of your point distribution and use that as your new point. Then repeat the process for the next two points.

Spatial Statistics>Measuring Geographic Distributions>Median Center

http://resources.arcgis.com/en/help/main/10.1/index.html#//005p00000019000000

I think you could accomplish this in Model Builder, although I have not used it in a while. It would be minimal code in Python if you run into issues with Model Builder.

model

Edit: I added a sample model you could use. I did this with a point dataset I created and it worked fine. What I think you will find is that the newly created points will be very close to one another (nearly coincident). Perhaps you have something else in mind for the additional points that I am not following.

Improve this answer
4
  • 1
    Could you please demonstrate that this works? It does not look like it should, unless you have something complicated in mind where you write "repeat the process."
    – whuber
    Commented Apr 14, 2013 at 18:49
  • Yeah, this will work for siting the first point, but I don't see how I can get the next two.
    – Wes
    Commented Apr 14, 2013 at 19:15
  • Why would repeating the process not work? Just take the median center from the first run and add it to the existing dataset. Run the median center on that and add it to the existing datset. Then run it again and add it to the dataset and you should have your final dataset. I will run it tonight and edit my answer.
    – TankofVines
    Commented Apr 14, 2013 at 21:39
  • 1
    This is not quite what I meant originally. The idea is to site three new points that would be distributed to minimize total sum difference, thus they would, I guess, be taking a subset of the total point set to find the median center of them. It would look something like this: i.imgur.com/0gKmlcG.png I did recreate and run your model, but it's not what I was trying to do. Thanks for the effort, though.
    – Wes
    Commented Apr 16, 2013 at 3:41
0

Probably to late to be useful to OP, but as a suggestion to future readers: I would recommend running k-means clustering, with k=3. these centroids would then be a reasonable place for your 3 points.

visualisation of k-means, source: https://www.geeksforgeeks.org/ml-k-means-algorithm/

source: https://www.geeksforgeeks.org/ml-k-means-algorithm/

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.