Fix two sets X and Y in the plane, each the interior of a curve, such that their closures don't intersect. How would one go about finding points x in X and y in Y such that the distance between X and Y is minimal?
Furthermore, say we have a bunch of sets X1, ..., Xn, each the interior of a curve, with nonintersecting closures. Let d(i,j) be the minimal distance between Xi and Xj. How can we find the minimal nonzero d(i,j), that is, the minimal distance between any two sets with nonintersecting closures? (In particular, there should be a faster algorithm than computing all the d(i,j). I suspect O(n log n) of the d(i,j) need to be computed although I have no idea why I'm saying this.)
The problem that inspired this is the following geographic one. What two states in the US that don't border each other are closest together? I think I know the answer; I'll post about that later.
Subscribe to:
Post Comments (Atom)
13 comments:
Off the top of my head, I'd think it'd have to be either New Jersey and Maryland (across Delaware) or New Jersey and Connecticut (across New York). Eyeballing it on the map, it looks like the Delaware crossing is slightly shorter, but they're pretty close to the same size.
I'll go for ny and ri out at the end of long island. Mass to Maine is also pretty short.
Life gets (more?) interesting if we are discussing closest in terms of driving.
I've got NY-CT down to 21.5 miles, measured with Google Maps. Neither endpoint is intuitive (according to me)
DE-NJ I have at 18.4, but a more intuitive route.
The most intuitive is MA - ME, and I get that under 18.
I suspect you may reverse these when you do "as the crow flies"
Jonathan
The northern tip of Virginia looks to be just over ~17 miles from Pennsylvania...
(google map link: http://tinyurl.com/dy6djt)
are the sets represented in finite form ? obviously for the US map example, they can be thought of as polygonal chains, but in general ?
I'm asking because you'd need to answer that question to do anything algorithmically. Your intuition about n log n is good, but even for computing the closest pair between points of two states (the bichromatic closest pair problem), I don't think there's an nlog n solution (if you're just looking the closest pair for a general collection of points, then n log n can be done, or linear time randomized)
Noah: NY and RI share a border out in the water.
jd: DE and NJ share a clear border. I think you might mean would be MD and NJ which seem to be about 10 miles
MA-ME seems to me more like 15 miles to me
What's a "border"? How about New Mexico and Utal or Arizona and Colorado? 0 miles
@ Carl -
Nope: the closures of the interiors of New Mexico and Utah intersect at one point, so they border each other under Michael's definition.
@ Michael -
It seems like you should only need to consider the points on the borders of the states. If this is true, it might reduce the number of points enough to make the problem brute-force crackable. Before you go looking for a fancy algorithm, I would give the naïve approach a try; in my experience, computers are often a lot faster than you expect them to be!
The advantage of driving distances is that there is a finite number of roads crossing a given border. From the computational point of view, different problem, right?
That's why my numbers (above) looked a bit high. And yes, unapologetic, I meant MD to NJ (skipping over Deleware).
Jonathan
This sounds similar to creating a Voronoi diagram.
I've got Virginia and Pennsylvania right about 17 or 18 as the crow flies.
I just found this blog a day or two ago and am catching up on old articles. This one, in particular, caught my attention because the title had me thinking something different before I got to the article.
My guess is DE-NJ, but ME-MA has possibilities, too, as does NY-RI.
[ ... ] link is being shared on Twitter right now. @zenx, an influential author, said RT @1ndus: Xtreme [ ... ]
Post a Comment