finding points close to points from n sets

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

fishboy - 30 Jun 2009 14:51 GMT

Suppose I have n sets of points in d (typically d=2) dimensions and I
would like to obtain a new set of points, each of which is close to
at
least one point from each of the n sets.

Graphically, for d=1. n=2

1 * 2 * 1

(numbers indicating the set from which the point is taken, the *
a new point). For d=2, n=3

2
1 * * 1
* 3
2

Nearest neighbours seems to be the obvious way to go for n=2,
but what about for n=3,4,...? Does this problem even have a name?

The application is practical (data synthesis) so pointers to
heuristics
would be most welcome

Thanks in advance!

Jim

Reply to this Message

Dan Luecking - 02 Jul 2009 19:32 GMT

>Suppose I have n sets of points in d (typically d=2) dimensions and I
>would like to obtain a new set of points, each of which is close to
[quoted text clipped - 15 lines]
>Nearest neighbours seems to be the obvious way to go for n=2,
>but what about for n=3,4,...? Does this problem even have a name?

I don't know about a name, but I think you need to
be a little more specific as to what you want the
new points to accomplish.

In your first example, assume the points in set 1
are at 0 and 2 and the point in set 2 is at 1. Then
the new points seem to be at .5 and 1.5. Thus both
have a distance .5 from both sets. However a single
new point placed at 1 would have a distance 0 from
set 2 and a distance 1 from set 1. Your choice
minimizes the _maximum_ distance, but both choices
minimize the _average_ distance to the two sets.

Thus, you need to specify what you wish the new
points to achieve, or at least a means to decide
when one set of new points is better than another.

Dan
To reply by email, change LookInSig to luecking

Reply to this Message

Math Forum / Mathematics / Research / July 2009

finding points close to points from n sets