MY work sometimes intervenes. I try to write my SearchResearch posts early in the morning before anything else can worm its way onto my schedule, but I didn't succeed yesterday. I've got a deadline coming up on Monday, and well... you know how it goes. Yesterday turned into a longish day and so I didn't get around to posting the hint I'd meant to share with you.
But here's the hint: Think geometrically.
I know, how long would it have taken to write that down yesterday?
Reminder: This week's challenge was to...
I have to tell you, the discussion on the Challenge was excellent. I did not know about the "Let's Meet in the Middle" app. Doing a search for:
[ travel equidistant tool ]
(as Fred did) was an excellent move. Everyone who did some variation on that theme gets a gold star because I didn't think of it, and I should have. That's just great!
The discussion about whether or not we should compute "crow flies" vs. "distance driven by car" was also excellent. (For the record, I meant just as the crow flies, but I like the fact that we discussed other options as possible solutions.)
To solve this problem, I started by searching out (as I hope you all did) the actual capitals of each of the states.
Didn't we all learn the state capitials in school? (At least the US kids should have.) We did, but memory is notoriously fallible. So it's worth checking, as Ramón did with his queries:
[California capital] A: Sacramento
[Washington capital ] A: Olympia
[Montana capital] A: Helena
[Nevada capital] A: Carson City
I suspect that many people will get the Washington and Nevada capitals wrong. Check your initial data to be sure you're solving the right problem.
Now my PLAN was to use a tool to just draw circles around each city, and then size them until I found a common meeting point.
So my first query was:
[ draw circles on Google Maps ]
and sure enough, I found a very nice circle-on-Google Maps drawing tool at MapDevelopers.com -- it lets you draw circles centered anywhere on the map. You can vary the radius and color. I put in the four cities and drew the following diagram. (There are the four capitals, each surrounded by a radius of a different amount. The fifth pin, midway between Helena and Seattle is a draggable pin, used to set the radius from the center.)
I quickly realized that the equidistant point was going to be somewhere around 400 miles away from each of the cities.... and I also realized that just fiddling with the radii wasn't a good strategy.
As I was telling someone else about my solution, I realized that I was implicitly trying to find the center of a circle with four points. And--this is the key point--three points define a circle with a common radius.
This was, in effect, a little remembrance of my old high school geometry. If three points lie on a circle, then the only point that is the same distance from all of them is in the center. Right? Let's call that distance r (for radius). A fourth point (say, a fourth city) that's NOT on the circle must be at some distance from the center of the circle that's NOT r distance away.
Just a glance at the diagram above shows that there can't possibly be any circle that fits all four of these points. You can fit three, just not these four.
So we have to think of a better solution than finding one point that's equidistant. What would that be?
My next query was to find a good method of computing the midpoint between four locations:
[ center between four points ]
and that's when I found my calculator: Geographic Midpoint.
And this map has (at the lower left) a nice set of options for determining HOW you want to define "midpoint."
Do you want "Center of Gravity"? "Center of minimum distance"? "Average lat/long"?
Here you can see I chose "Center of gravity," which is (I looked it up) the balance point of a figure that's defined by its shape. That's the blue dot above. We could have used the average of the lat/long (in effect, looking for the midpoint of the lines), or we could have computed the Centroid. But they all would be about the same, pointing to a location in southern Oregon.
You can read a lengthy discussion about the tradeoffs and ways to compute the midpoints. (Which Ramón pointed to in his comments.)
Of course, we could also have taken the lat/longs for each city, and computed the intersection of diagonals. For a roughly trapezoidal shape (as you see above), it wouldn't be that far off.
Helena:
I'll leave it as an exercise for the reader (who remembers high school geometry) to compute the intersection of the two lines.
Search Lessons:
There's a big one here for me: This wasn't at all what I'd expected the answer to be! When I wrote it up, I figured it would be a simple process to take a Google Map and drop in a few circles, compute the distance, and be done with it.
Moral for people who write questions (I'm looking at you, teachers!), problems often are much more challenging that you first think.
I'm really pleased that we found so many alternate solutions!
I have to admit that I hadn't thought about the "How Far Can I Drive" aspect of the problem. But clearly, if you're going to live there, that's a great factor to consider.
And I really hadn't dreamed that there would be a tool to compute this, although now I know about it.
Excellent finds and analysis from everyone. Nicely done.
(But of course, be sure to check your state capitals.)
And the last lesson, of course, has to be: You never know when geometry will be needed.
Search on!
But here's the hint: Think geometrically.
I know, how long would it have taken to write that down yesterday?
Reminder: This week's challenge was to...
1. Can you find the place that's "in the middle" of all four cities? (The capitals of California, Washington, Nevada, and Montana.) That is, find the place you'd like to live that's equidistant from all four city centers. (Feel free to ignore curvature of the Earth effects.)
I have to tell you, the discussion on the Challenge was excellent. I did not know about the "Let's Meet in the Middle" app. Doing a search for:
[ travel equidistant tool ]
(as Fred did) was an excellent move. Everyone who did some variation on that theme gets a gold star because I didn't think of it, and I should have. That's just great!
The discussion about whether or not we should compute "crow flies" vs. "distance driven by car" was also excellent. (For the record, I meant just as the crow flies, but I like the fact that we discussed other options as possible solutions.)
To solve this problem, I started by searching out (as I hope you all did) the actual capitals of each of the states.
Didn't we all learn the state capitials in school? (At least the US kids should have.) We did, but memory is notoriously fallible. So it's worth checking, as Ramón did with his queries:
[California capital] A: Sacramento
[Washington capital ] A: Olympia
[Montana capital] A: Helena
[Nevada capital] A: Carson City
I suspect that many people will get the Washington and Nevada capitals wrong. Check your initial data to be sure you're solving the right problem.
Now my PLAN was to use a tool to just draw circles around each city, and then size them until I found a common meeting point.
So my first query was:
[ draw circles on Google Maps ]
and sure enough, I found a very nice circle-on-Google Maps drawing tool at MapDevelopers.com -- it lets you draw circles centered anywhere on the map. You can vary the radius and color. I put in the four cities and drew the following diagram. (There are the four capitals, each surrounded by a radius of a different amount. The fifth pin, midway between Helena and Seattle is a draggable pin, used to set the radius from the center.)
I quickly realized that the equidistant point was going to be somewhere around 400 miles away from each of the cities.... and I also realized that just fiddling with the radii wasn't a good strategy.
As I was telling someone else about my solution, I realized that I was implicitly trying to find the center of a circle with four points. And--this is the key point--three points define a circle with a common radius.
This was, in effect, a little remembrance of my old high school geometry. If three points lie on a circle, then the only point that is the same distance from all of them is in the center. Right? Let's call that distance r (for radius). A fourth point (say, a fourth city) that's NOT on the circle must be at some distance from the center of the circle that's NOT r distance away.
Just a glance at the diagram above shows that there can't possibly be any circle that fits all four of these points. You can fit three, just not these four.
So we have to think of a better solution than finding one point that's equidistant. What would that be?
My next query was to find a good method of computing the midpoint between four locations:
[ center between four points ]
and that's when I found my calculator: Geographic Midpoint.
And this map has (at the lower left) a nice set of options for determining HOW you want to define "midpoint."
Do you want "Center of Gravity"? "Center of minimum distance"? "Average lat/long"?
Here you can see I chose "Center of gravity," which is (I looked it up) the balance point of a figure that's defined by its shape. That's the blue dot above. We could have used the average of the lat/long (in effect, looking for the midpoint of the lines), or we could have computed the Centroid. But they all would be about the same, pointing to a location in southern Oregon.
You can read a lengthy discussion about the tradeoffs and ways to compute the midpoints. (Which Ramón pointed to in his comments.)
Of course, we could also have taken the lat/longs for each city, and computed the intersection of diagonals. For a roughly trapezoidal shape (as you see above), it wouldn't be that far off.
Helena:
46.595806, -112.027031
Sacramento:
38.555556, -121.468889
Carson City:
39.160833, -119.753889
Olympia:
47.042500, -122.893056
I'll leave it as an exercise for the reader (who remembers high school geometry) to compute the intersection of the two lines.
Search Lessons:
There's a big one here for me: This wasn't at all what I'd expected the answer to be! When I wrote it up, I figured it would be a simple process to take a Google Map and drop in a few circles, compute the distance, and be done with it.
Moral for people who write questions (I'm looking at you, teachers!), problems often are much more challenging that you first think.
I'm really pleased that we found so many alternate solutions!
I have to admit that I hadn't thought about the "How Far Can I Drive" aspect of the problem. But clearly, if you're going to live there, that's a great factor to consider.
And I really hadn't dreamed that there would be a tool to compute this, although now I know about it.
Excellent finds and analysis from everyone. Nicely done.
(But of course, be sure to check your state capitals.)
And the last lesson, of course, has to be: You never know when geometry will be needed.
Search on!
A friend just directed me to this page. With regard to your remark:
ReplyDelete"Moral for people who write questions (I'm looking at you, teachers!), problems often are much more challenging that you first think."
Incidentally, I write up a lesson plan on the case for three places (at the behest of Teachers College's Dr. Bruce Vogeli and Dr. Henry Pollak). You can find a copy here: http://www.iitgn.ac.in/mcm/cd/Mathematical%20Modelling%20Handbook/pdf/11_Treasure.pdf Check the last paragraph of the last page for a bit of historical context.
You can also find a similar bit in my background example here: http://mathoverflow.net/q/104714/22971 Note that I introduce the term "geometric median" in that post; by searching for this term on Wikipedia, you can find the method to solve the problem here.
In particular, see: http://en.wikipedia.org/wiki/Geometric_median#Special_cases
"For 4 coplanar points, if one of the four points is inside the triangle formed by the other three points, then the geometric median is that point. Otherwise, the four points form a convex quadrilateral and the geometric median is the crossing point of the diagonals of the quadrilateral. The geometric median of four coplanar points is the same as the unique Radon point of the four points."