Re: Disjoint circle merge NP complete for L^n error?
- From: Ralph Hartley <hartley@xxxxxxxxxxxxxxxx>
- Date: Thu, 30 Jun 2005 12:54:18 -0400
Torben Ægidius Mogensen wrote:
> "Gene" <eugene.ressler@xxxxxxxxxxxxxxx> writes:
>>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.
....
> 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.
But the result will depend strongly on the order in which they are
merged, and some orders will lead to dead ends with worse than minimal
cost. Trying all possible orders is exponential.
>> * 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?
The freedom is in assigning points to circles.
The error function reflects the fact that you want the points to be as
close to the center of the their circles as possible.
This looks similar to the problem of half toning. There you are given an
image and want to produce a pattern of black and white (with some
constraints) that approximates it as well as possible (according to some
criterion). I haven't followed the recent literature on that problem myself.
>>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?
Not if I understand correctly. The position of the circle is required to
be the center of gravity of its points, and its area is proportional to
its population.
Moving a point from one circle to another changes the size and position
of both circles.
You *could* allow the positions and sizes circles to vary, or to overlap
a little, with penalties in the evaluation function, but it isn't clear
that it would make the problem any easier.
>>But, we really need to generalize the error definition from MAX (i.e.
>>L^\infty) to L^n. For example, replace MAX with SUM.
The obvious one is L^2.
My guess is that the problem is NP complete (for any reasonable error
function).
>> 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.)
(pause while I read your proof)
Make the wires thicker.
For example, a Double Wire connecting 4 single wires:
---x---x---
| |
---x---x---
x=Tee
If the thickness of a wire is proportional to the number of clauses it
connects then the cost of breaking it will be greater than the benefit
of satisfying the clauses.
You can also make the wires slightly stronger than the clauses by
allowing their circles to overlap slightly, instead of just touching,
but I don't think you need to.
Even if the problem is NP complete, remember that most instances you see
in real life may be very easy. Some sort of gradient descent, or
simulated annealing, or etc. should do just fine.
Ralph Hartley
.
- Follow-Ups:
- References:
- Disjoint circle merge NP complete for L^n error?
- From: Gene
- Re: Disjoint circle merge NP complete for L^n error?
- From: Torben Ægidius Mogensen
- Disjoint circle merge NP complete for L^n error?
- Prev by Date: Re: Disjoint circle merge NP complete for L^n error?
- Next by Date: Re: Disjoint circle merge NP complete for L^n error?
- Previous by thread: Re: Disjoint circle merge NP complete for L^n error?
- Next by thread: Re: Disjoint circle merge NP complete for L^n error?
- Index(es):
Relevant Pages
|
