finding points close to points from n sets

[fishboy]

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

[Dan Luecking]

On Tue, 30 Jun 2009 15:00:01 +0100 (BST), fishboy
<j.j.f...@gmail.com> wrote:

>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?

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