MATLAB Central Newsreader - evenly distributed subset of points on a sphere

evenly distributed subset of points on a sphere

Abel Brown — Fri, 30 Oct 2009 14:43:05 -0400

I have, say, 250 points ~ evenly distributed around the globe (x,y,z coordinates). I would like to choose N subsets of these points are are also evenly distributed. I'v been wracking my brain for a few days now and I can't really think of an elegant way to do this.

Anyone know a reasonable way to tackle this?

cheers!

Re: evenly distributed subset of points on a sphere

Matt — Fri, 30 Oct 2009 15:03:03 -0400

"Abel Brown" <brown.2179@osu.edu> wrote in message <hceu1p$f13$1@fred.mathworks.com>...
> I have, say, 250 points ~ evenly distributed around the globe (x,y,z coordinates). I would like to choose N subsets of these points are are also evenly distributed. I'v been wracking my brain for a few days now and I can't really think of an elegant way to do this.
>
> Anyone know a reasonable way to tackle this?

It sounds like a solution might not exist, unless I'm misunderstanding what you mean by "evenly distributed".

Suppose you only had 4 evenly distributed points instead of 250. Clearly no subset of the 4 is evenly distributed.

Re: evenly distributed subset of points on a sphere

Abel Brown — Fri, 30 Oct 2009 15:17:01 -0400

For sure, I understand the limiting factors. The initial set of points to choose from would never be less than 75.

The number of points will always be much much greater than the number of subsets.

For instance, my example of 250 points. 6 would definitely be max number of subsets I would ever need. That's a ratio of like 6/250 = 0.025.

Even just an approximation/ball park would be great.

Re: evenly distributed subset of points on a sphere

Matt — Fri, 30 Oct 2009 15:35:18 -0400

"Abel Brown" <brown.2179@osu.edu> wrote in message <hcf01c$kru$1@fred.mathworks.com>...
> For sure, I understand the limiting factors. The initial set of points to choose from would never be less than 75.
>
> The number of points will always be much much greater than the number of subsets.
>
> For instance, my example of 250 points. 6 would definitely be max number of subsets I would ever need. That's a ratio of like 6/250 = 0.025.
----

I don't see how it's an issue of the number of subsets.

It's at least partly an issue of the number of points belonging to the subsets. For example, in your case of 250 points, suppose you said that you wanted each of the 6 subsets to contain 249 points. This is equivalent to the problem of choosing one of the 250 points to remove so that the remaining 249 are evenly distributed over the sphere, which is again clearly impossible.

Re: evenly distributed subset of points on a sphere

Abel Brown — Fri, 30 Oct 2009 15:45:06 -0400

You're over complicating the issue.

250 points evenly distributed over the globe. I need to break these 250 points into 5-6 evenly distributed subsets or networks. So 250/6 would be about 40 points in each subset.

I just want to partition the the original 250 point network into 6 subnetworks or subsets that are themselves evenly distributed.

Re: evenly distributed subset of points on a sphere

Matt — Fri, 30 Oct 2009 15:56:02 -0400

"Abel Brown" <brown.2179@osu.edu> wrote in message <hcf1m2$32o$1@fred.mathworks.com>...
>
> You're over complicating the issue.
>
> 250 points evenly distributed over the globe. I need to break these 250 points into 5-6 evenly distributed subsets or networks. So 250/6 would be about 40 points in each subset.
>
> I just want to partition the the original 250 point network into 6 subnetworks or subsets that are themselves evenly distributed.
================

How is that less complicated than the hypotheticals I gave you?

In any case, since you seem to have a tool for generating set S1 of 250 even-spaced points, you presumably can generate a second set S2 of 40 evenly spaced points as well. You can then find take the closest point in S1 to each point in S2 and call that your subset. Since you've said you'd be happy with a ball-park solution, this seems to be a perfectly valid candidate.

Re: evenly distributed subset of points on a sphere

Abel Brown — Fri, 30 Oct 2009 16:09:02 -0400

LOL, I did not generate this set of 250 points.

This is a little strange. You seem to be avoiding the question. I need a practical solution not a mathematical proof.

250 evenly distributed around the earth. Need to divide these 250 points into 6 subsets or subnetworks of ~ 250/6 = 40 points each which are themselves evenly distributed around the earth.

Indeed, generate 40 evenly distributed points on a sphere and choose closes points in super set. Easy enough ... but how to generate 40 evenly distributed points around the earth?

Re: evenly distributed subset of points on a sphere

Matt Fetterman — Fri, 30 Oct 2009 16:33:22 -0400

"Abel Brown" <brown.2179@osu.edu> wrote in message <hcf32u$10a$1@fred.mathworks.com>...
> LOL, I did not generate this set of 250 points.
>
> This is a little strange. You seem to be avoiding the question. I need a practical solution not a mathematical proof.
>
> 250 evenly distributed around the earth. Need to divide these 250 points into 6 subsets or subnetworks of ~ 250/6 = 40 points each which are themselves evenly distributed around the earth.
>
> Indeed, generate 40 evenly distributed points on a sphere and choose closes points in super set. Easy enough ... but how to generate 40 evenly distributed points around the earth?

If you google it, you will find that the problem is surprisingly challenging, so there is no simple answer here.
One interesting webpage is here, I think the optimization technique might work reasonably well. Regards! Matt
http://www.math.niu.edu/~rusin/known-math/94/equi_holes

Re: evenly distributed subset of points on a sphere

Matt — Fri, 30 Oct 2009 16:45:19 -0400

"Abel Brown" <brown.2179@osu.edu> wrote in message

> This is a little strange. You seem to be avoiding the question. I need a practical solution not a mathematical proof.
====

Well, no, I'm just learning very slowly from you what the situation is, i.e. where these points come from (you've only now informed us that you didn't generate them yourself), what level of error you're prepared to accept since an exact solution might be impossible (you've told me you'll accept a ballpark solution but not how inexact it can be) etc... All these things have a bearing on what solution approach we can take.

Re: evenly distributed subset of points on a sphere

ImageAnalyst — Fri, 30 Oct 2009 16:48:27 -0400

On Oct 30, 12:09 pm, "Abel Brown" <brown.2...@osu.edu> wrote:
> LOL, I did not generate this set of 250 points.
>
> This is a little strange. You seem to be avoiding the question. I need a practical solution not a mathematical proof.
>
> 250 evenly distributed around the earth. Need to divide these 250 points into 6 subsets or subnetworks of ~ 250/6 = 40 points each which are themselves evenly distributed around the earth.
>
> Indeed, generate 40 evenly distributed points on a sphere and choose closes points in super set. Easy enough ... but how to generate 40 evenly distributed points around the earth?

--------------------------------------------------------------------------------------------------------------------------------------------------
Abel:
I would imagine that you'd just take every 6th point in the Z
direction. Visualize this: you have a bunch (say 250) of points more
or less randomly distributed around the surface of the globe. Now
imagine that you take a string and fasten it to the point closest to
the North Pole. Now spiral that string around the globe such that it
traverses every point, say as the string is going from east to west as
you wind the string around the globe clockwise (looking down from the
top). So now every point on the globe is ordered as to its location
on the string. Now assuming your initial set was fairly randomly and
uniformly distributed, I think you could get one set which consists of
points
1, 7, 13, 19, 25, etc.
The second set would be one over from that:
2, 8, 14, 20, 26, etc.
and the third set would consist of points
3, 9, 15, 21, 27, etc.
and so on. Imagine that each set was identified by different colored
beads on the surface of the globe. It seems like the set of (say) red
beads (taken starting with location 1) would be approximately just as
uniformly scattered as the (say) green beads (take starting with
location 2), and so on. Every set of different colored beads would be
about as randomly and uniformly positioned as any other set.

Because we picked up the points by spiraling down, subsequent points
have decreasing Z values (latitude). So all you need to do is to sort
your array of x,y,z coordinates by the z value and then take every nth
point. Other sets just start at a different point before taking every
nth point, like my example above. Does that make sense - do you
follow me? Does that seem like it will work well enough for you?
Might be worth a try and see how it goes.
Regards,
ImageAnalyst

Re: evenly distributed subset of points on a sphere

Abel Brown — Fri, 30 Oct 2009 17:47:03 -0400

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <067a12b6-b55b-40b8-8c9c-474d70729e13@p8g2000yqb.googlegroups.com>...
> On Oct 30, 12:09?pm, "Abel Brown" <brown.2...@osu.edu> wrote:
> > LOL, I did not generate this set of 250 points. ?
> >
> > This is a little strange. ?You seem to be avoiding the question. I need a practical solution not a mathematical proof. ?
> >
> > 250 evenly distributed around the earth. ?Need to divide these 250 points into 6 subsets or subnetworks of ~ 250/6 = 40 points each which are themselves evenly distributed around the earth.
> >
> > Indeed, generate 40 evenly distributed points on a sphere and choose closes points in super set. ?Easy enough ... but how to generate 40 evenly distributed points around the earth?
>
> --------------------------------------------------------------------------------------------------------------------------------------------------
> Abel:
> I would imagine that you'd just take every 6th point in the Z
> direction. Visualize this: you have a bunch (say 250) of points more
> or less randomly distributed around the surface of the globe. Now
> imagine that you take a string and fasten it to the point closest to
> the North Pole. Now spiral that string around the globe such that it
> traverses every point, say as the string is going from east to west as
> you wind the string around the globe clockwise (looking down from the
> top). So now every point on the globe is ordered as to its location
> on the string. Now assuming your initial set was fairly randomly and
> uniformly distributed, I think you could get one set which consists of
> points
> 1, 7, 13, 19, 25, etc.
> The second set would be one over from that:
> 2, 8, 14, 20, 26, etc.
> and the third set would consist of points
> 3, 9, 15, 21, 27, etc.
> and so on. Imagine that each set was identified by different colored
> beads on the surface of the globe. It seems like the set of (say) red
> beads (taken starting with location 1) would be approximately just as
> uniformly scattered as the (say) green beads (take starting with
> location 2), and so on. Every set of different colored beads would be
> about as randomly and uniformly positioned as any other set.
>
> Because we picked up the points by spiraling down, subsequent points
> have decreasing Z values (latitude). So all you need to do is to sort
> your array of x,y,z coordinates by the z value and then take every nth
> point. Other sets just start at a different point before taking every
> nth point, like my example above. Does that make sense - do you
> follow me? Does that seem like it will work well enough for you?
> Might be worth a try and see how it goes.
> Regards,
> ImageAnalyst

Brilliant! I really like this idea! Nice and simple. I'll give it a try and let you know how it works out.

Fetterman: Thanks for your reply! Indeed, I did some reading/googling before posting and pretty much all of the algorithms I found were overkill. Many folks on the forum have tremendous practical experience. It's always interesting to see what solutions come up!

Thanks again!

Re: evenly distributed subset of points on a sphere

Bruno Luong — Fri, 30 Oct 2009 18:18:19 -0400

"Matt Fetterman" <mattinjersey@yahoo.com> wrote in message <hcf4gi$rcc$1@fred.mathworks.com>...

> One interesting webpage is here, I think the optimization technique might work reasonably well. Regards! Matt

I can't believe such minimization technique hasn't yet available. I think I'll code it and make it available for the community (if it requires a reasonable amount of work).

Bruno