Re: Disjoint circle merge NP complete for L^n error?

"Gene" <eugene.ressler@xxxxxxxxxxxxxxx> writes:

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

You can do this iteratively: Start with groups of circles that overlap
and combine these. If this creates more overlaps, repeat. This
should have low-order polynomial complexity.

> * some error function is minimized.

If the new circle is centered on the combined CoG and the area is the
sum of the areas, there is no freedom over which to minimize a
function. Or do you allow the position, area or both of the circles
to be inexact?

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

This indicates that the positioning can be inexact. Can the areas be
too? And is th eobject of introducing the error function to minimize
the number of mergings?

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

It is really hard to give a definite answer without more details,
i.e., what parameters (area, placement) can be flexible and what the
error function looks like. In the simlest case, it might be solvable
by linear programming, but I suspect (as you) that most instances are
NP-hard.

Torben

.

Relevant Pages

  • Re: Disjoint circle merge NP complete for L^n error?
    ... >>I have a real cartography problem where an NP completeness proof would ... Or do you allow the position, area or both of the circles ... The error function reflects the fact that you want the points to be as ... Make the wires thicker. ...
    (comp.theory)
  • Re: Disjoint circle merge NP complete for L^n error?
    ... >> should have low-order polynomial complexity. ... Or do you allow the position, area or both of the circles ... let us look at the simple case (with no error function). ... - Joining circles is associative: If you first join a and b and then ...
    (comp.theory)
  • [C++] Member function headache
    ... overlap (areas can be rectangles, circles, points...). ... The problem is that when I have a rectangle class which has an overlap ... make circles overlap funtion like this: ...
    (alt.comp.lang.learn.c-cpp)
  • Re: Proportional Venn Diagrams
    ... circles' areas and the overlapping portion to be proportionate to their ... Since you say B and C are entirely inside A, your problem boils down to getting just two circles to overlap. ... You can get the proportionality of the circles easily enough using a Bubble Chart type, but Excel bubble charts don't preserve the relationship between bubble radius and XY scale properly, so trigonometry wouldn't work there. ...
    (microsoft.public.excel.charting)
  • Re: Venn diagrams in Visio?
    ... - Draw your ovals (Venn diagram symbols), the way they overlap like you want ... Select both ovals ... > overlapping circles as components, with parts of the circles filled ... > the two circles overlap. ...
    (microsoft.public.visio.general)