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

Groups > comp.programming > #341

Re: Select well-distributed points from ill-distributed set

Show all headers | View raw

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

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web