Math help, please. Here’s the problem.
You have a circle with a diameter of 80 miles. You have 100 points somewhere on or in that circle. You need to travel to all 100 points. You can start at any point and don’t need to return there - when you reach the last point you’re done. You want to travel as short a total distance as possible (or something close to that) as you travel to all 100 points.
Is it possible to calculate the maximum distance which would be the shortest route to all 100 points? And is it possible then to calculate the highest possible average distance traveled between points?
Here’s what I did, I don’t know if this is right. The diameter = 80. Set pi as 3.15 for the sake of cleaner numbers. The circumference then is 252. I could be wrong, but I think the largest possible distance would if you had 99 points around the circumference and 1 at the center. You would travel the circumference, 252 miles, then travel 40 miles to the center (or travel from the center to some point on the circumference then travel the circumference) for a total of 292 miles. In that case, you travel an average of 2.92 miles between points.
Did I make a mistake here?
I’m no geometrician, but it seems you would cut off some distance by travelling straight lines between the points on the edge. I’m intrigued as to the purpose of this problem…
Comment by Mike B — July 13, 2007 @ 11:15 pm
Your solution is correct as the minimum of all the sums of shortest distances between the points. Because otherwise it depends on from which point you start. For instance, say you move one of the 99 points away from the circumference and place it at distance 30 from the center. Starting from the displaced point you get 10 + 252(almost) + 40 = 302(almost), which is larger than 292(almost) that you get if you start from the center. So, unless you get the minimal maximal distance, your situation is rather path dependent (as they say in complexity theory, economics and historical sociology).
Comment by Mo — July 14, 2007 @ 2:49 am
Thanks for the help y’all.
Mike, there’s not much purpose really. Here’s the origin of my wondering. I was thinking about what it would take to talk to every single worker at a facility. A small group working at the facility is limited by the amount of time they have outside of work per week (person hours per week is low). If a group could come in from out of town to help for a weekend, the number of total person hours expendable that weekend is higher. During that weekend, of course, one would want to be as efficient as possible with the out of towners’ time. I just made up some numbers - 100 employee plant, everyone lives 40 miles or less from the plant, can we calculate rough distances etc, so we can set some basic benchmarks for how many people we’d need from out of town to really maximize the weekend. 100 people living 40 miles or less from work, means we can expect an average of 3 miles or so between people’s homes. Four cars visiting those folk would have 25 people each, are likely to drive 75 miles during the day. If they drive an average of 30ish miles an hour, they’re going to spend about 2 1/2 hours driving so they need to spend enough time knocking doors to make it worth the drive time. Etc. Make sense? Like I said, I started thinking about all this and just got caught up on the math question.
take it easy,
Nate
Comment by Nate — July 15, 2007 @ 2:38 pm
What is this, like anti-Taylorism?
Comment by Mark — July 17, 2007 @ 4:48 am
I prefer to call it Rolyatism.
Comment by Nate — July 17, 2007 @ 12:18 pm