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

Groups > comp.programming > #355

I like noise

Show all headers | View raw

… 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.

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