Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #340 > unrolled thread

Select well-distributed points from ill-distributed set

Back to article view | Back to comp.programming

Contents

  Select well-distributed points from ill-distributed set Michael Schmid <michael.schmid@geod.baug.ethz.ch> - 2011-05-20 16:26 +0200
    Re: Select well-distributed points from ill-distributed set James Waldby <not@valid.invalid> - 2011-05-20 15:25 +0000
      Convex hull presents difficulties Michael Schmid <michael.schmid@geod.baug.ethz.ch> - 2011-05-23 15:02 +0200
    Re: Select well-distributed points from ill-distributed set "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-05-21 10:56 +0100
      Closest-pair approach works fine Michael Schmid <michael.schmid@geod.baug.ethz.ch> - 2011-05-23 15:21 +0200
        Re: Closest-pair approach works fine "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-05-23 14:49 +0100
          I like noise Michael Schmid <michael.schmid@geod.baug.ethz.ch> - 2011-05-24 08:32 +0200
            Re: I like noise Patricia Shanahan <pats@acm.org> - 2011-05-24 20:18 -0700
    Re: Select well-distributed points from ill-distributed set jebblue <n@n.nnn> - 2011-05-22 00:30 -0500

#340 — Select well-distributed points from ill-distributed set

From a set of irregularly distributed points I want to choose a given number
which are well-distributed, in the sense that the distances in between
these selected points are maximised in some way. For example, if I have a
dense cluster of 20 points, and one point lying at a big distance from the
cluster, and I want to select four points out of this set, a good solution
would probably include that outlier as well as three points from the
cluster lying far apart from each other. I do not necessarily need the best
solution, a good one would suffice. Does anyone have a tip for a heuristic
(or a fast deterministic) algorithm?

In my application, the set of points are hundreds of GPS receivers
distributed over the Earth. In the northern hemisphere, they are quite
dense, whereas in oceans they are rather sparse. I want to select about 50
out of them to do some analysis. However, the total set of available
stations as well as the number of stations used change occasionally, which
is why I want to automate the selection process.

[toc] | [next] | [standalone]

#341

On Fri, 20 May 2011 16:26:31 +0200, Michael Schmid wrote:
> From a set of irregularly distributed points I want to choose a given
> number which are well-distributed, in the sense that the distances in
> between these selected points are maximised in some way. For example, if
> I have a dense cluster of 20 points, and one point lying at a big
> distance from the cluster, and I want to select four points out of this
> set, a good solution would probably include that outlier as well as
> three points from the cluster lying far apart from each other. I do not
> necessarily need the best solution, a good one would suffice. Does
> anyone have a tip for a heuristic (or a fast deterministic) algorithm?
> 
> In my application, the set of points are hundreds of GPS receivers
> distributed over the Earth. In the northern hemisphere, they are quite
> dense, whereas in oceans they are rather sparse. I want to select about
> 50 out of them to do some analysis. However, the total set of available
> stations as well as the number of stations used change occasionally,
> which is why I want to automate the selection process.

Perhaps consider thinning the set of points via convex hull
in Theta(n * lg h) time, for h points in hull of set of n points,
via eg <http://en.wikipedia.org/wiki/Chan%27s_algorithm>.

In your 20+points+outlier example, the outlier would (in most
cases) be in the hull, and points not in the hull generally are
more closely clustered than those in the hull.

Which points are in the hull can depend on what map projection
you use but if all the receivers are in one hemisphere many 
projections will give the same results. 


-- 
jiw

[toc] | [prev] | [next] | [standalone]

#351 — Convex hull presents difficulties

Thank you for your idea, James. I am, however, not completely convinced yet
by your convex-hull approach for the point selection problem; maybe I
misunderstand you.

1. Two points lying on the hull might be very close together. Choosing one
   from the centre of the cluster instead would give a better distribution.

2. How do I make sure that I get the desired number of points selected?

3. In my application, the points lie on a closed surface, on which I am not
   sure how to define a convex hull.

[toc] | [prev] | [next] | [standalone]

#347

Michael Schmid wrote:

> In my application, the set of points are hundreds of GPS receivers
> distributed over the Earth. In the northern hemisphere, they are quite
> dense, whereas in oceans they are rather sparse. I want to select about 50
> out of them to do some analysis. However, the total set of available
> stations as well as the number of stations used change occasionally, which
> is why I want to automate the selection process.

Since you have fairly small numbers, perhaps you could do something brutish 
like:

Start with all your points.
While you have too many points do:
    select the pair of points which are closest to each other.
    remove one of them [*].
    repeat.

At the step [*] you could choose arbitrarily, or make a more informed selection 
by, say, considering the distance to their second closest neighbours,

Probably there's a way to optimise the "find the closest pair of points" step, 
but I don't know it.

    -- chris 

[toc] | [prev] | [next] | [standalone]

#352 — Closest-pair approach works fine

Thank you, Chris! This works very well in my 20-points-plus-outlier example.

Whether the informed selection for the removal step is required depends on
the ratio between the selected number of points and the total number. The
lower this ratio is, the more beneficial the informed selection is.
When using the informed selection, I removed the point which is closer to a
third one, as you suggested.

It should also be easy to adapt this to a non-euclidean geometry (such as
the earth’s surface) by simply modifying the distance function used for
finding both the closest pair and the third nearest neighbor.

[toc] | [prev] | [next] | [standalone]

#353 — Re: Closest-pair approach works fine

Michael Schmid wrote:

> Whether the informed selection for the removal step is required depends on
> the ratio between the selected number of points and the total number. The
> lower this ratio is, the more beneficial the informed selection is.
> When using the informed selection, I removed the point which is closer to
> a third one, as you suggested.

I'm glad it helped.  So here's another suggestion :)

Still on the assumption that the dataset is small enough (or the time available 
is large enough) to contemplate O(n^2) algorithms.

Imagine that each station generates "noise" which is picked up by all the other 
stations.  You could imagine that the noise fell off in an inverse-square ratio 
like real noise.

Compute how much noise each station recieves from all the others (which is 
O(n^2) in space and time).  While you have more stations than you want, remove 
the station which is "hearing" the most noise (i.e. the one which is in some 
sense closest to all the others), and remove its contribution from the noise 
levels experienced by the remaing stations. Repeat.

It might be better or it might be worse...

    -- chris 

[toc] | [prev] | [next] | [standalone]

#355 — I like noise

… well, usually not, but in this case I do.

The results are different than those from the closest-pair approach, but
comparable in quality. When I sum up the distances between the selected
points, sometimes one method is slightly better, sometimes the other,
depending on the point set and the number of points to be selected.

However, the noise implementation runs about five times faster. The speed
benefit is more significant the more points are excluded, as with the noise
algorithm, only a few summations take place in every iteration, whereas the
closest-pair approach does quite a bit more. But even with only one point
to remove, the noise approach is faster.

Furthermore, it is more straightforward to implement, without need for
sophisticated algorithms to find the closest pair or the k nearest
neighbors.

I tried out both inverse-distance and inverse-square-distance functions, and
found that the inverse-square gives better results, but I don’t exactly
know why.

[toc] | [prev] | [next] | [standalone]

#356 — Re: I like noise

On 5/23/2011 11:32 PM, Michael Schmid wrote:
...
> I tried out both inverse-distance and inverse-square-distance functions, and
> found that the inverse-square gives better results, but I don’t exactly
> know why.

You might try inverse-cube, or higher power. The higher the exponent,
the greater the weight given to nearby points relative to distant points
in calculating the total noise at a point.

Patricia

[toc] | [prev] | [next] | [standalone]

#348

On Fri, 20 May 2011 16:26:31 +0200, Michael Schmid wrote:

> From a set of irregularly distributed points I want to choose a given
> number which are well-distributed, in the sense that the distances in
> between these selected points are maximised in some way. For example, if
> I have a dense cluster of 20 points, and one point lying at a big
> distance from the cluster, and I want to select four points out of this
> set, a good solution would probably include that outlier as well as
> three points from the cluster lying far apart from each other. I do not
> necessarily need the best solution, a good one would suffice. Does
> anyone have a tip for a heuristic (or a fast deterministic) algorithm?
> 
> In my application, the set of points are hundreds of GPS receivers
> distributed over the Earth. In the northern hemisphere, they are quite
> dense, whereas in oceans they are rather sparse. I want to select about
> 50 out of them to do some analysis. However, the total set of available
> stations as well as the number of stations used change occasionally,
> which is why I want to automate the selection process.

I'd drop the outliers.

-- 
// This is my opinion.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web