Disjoint circle merge NP complete for L^n error?

Hello!

I have a real cartography problem where an NP completeness proof would
be a great help, but don't do these often; hence the question.

We have a large set of real triples (x,y,pop) and represent them on a
map with circles of area pop at location (x,y). Inevitably, circles
overlap (as the scale of the map gets smaller, the problem gets worse)
so we set out to find an algorithm that partitions the tuples such that
each subset S is represented by a single circle at the center of mass
of S with
* area = sum_{t\in S}(t.pop)
* no other circle is touched,
* some error function is minimized.
For example, two tuples (0,0,1) and (1,2,1) lead to circles that
overlap and so in a partition might be represented as a single circle
of radius \sqrt{2} centered at (1/2,1). (If we double the scale the
tuples become (0,0,1) (2,4,1) and the overlap goes away, but this is
not an option.)

The error function is the issue. We have a proof of NP completeness for
the related DP with MAX Euclidean distance between a single population
member and the center of its representing circle. See
http://www.frontiernet.net/~eugene.ressler/circles.pdf .

But, we really need to generalize the error definition from MAX (i.e.
L^\infty) to L^n. For example, replace MAX with SUM. With even this
simple change however the construction at the link above falls apart!
(A "wire" can be broken with the error this introduces made up by a
number of erroneously satisfied clauses.)

Any insights appreciated...

Kindest regards,
GR

.

Relevant Pages