Coverage maximization algorithm, minimizing element usage?

Question

I have a scenario that you can imagine as follows:

Start with an image with a height of 100 pixels by 1000 pixels. In addition to this image, you have a set of cropped sections of this image. Each section has a width of 100 pixels and a height of 100 pixels. Part of the image contained in the section is changing. For example, you might have one that starts at the very top (pixel 0), then one on vertical pixel 3, then one on vertical pixel 9, etc.

What I need to do is find a way to look at the set of smaller images and select the fewest sections that will give me the most coverage of the original image.

A few notes:

• Image content is not a big deal. It really matches the coordinates that matter.
• When restoring, there will never be gaps in the image, but there may not be enough parts to reach the bottom.
• There will be many overlaps between sections. In fact, there will be cases when there will be only one pixel or two (vertical) markup between two sections.

Can someone point me in the right direction? I can do such brute force ... but I guess there is a better way.

Answer 1

Sorry, but I don’t understand why this problem is NP-hard.

The general idea is that you iteratively delete the lower parts of your image by selecting the “best” section, that is

• ,
• ( ), .

. - (0,1,3,10,..., 988,999), 0 , . ( , 999, )

, 100xN. N = 1000.

n - , : i.e n - , , n + 100 >= N. , n - .

(0,1,... 899, 900, 901,.., 999), n = 900

(0,1,... 899, 905, 910,.., 999), n = 905

(0,1,..., 888,898,), n = 898

N = n ( ) (, , " >= n" )

, (100 ) NP-.

Answer 2

, http://en.wikipedia.org/wiki/Maximum_coverage_problem - ( , -).

100x1000, NP-hard, , P . , , O(N) , , O(N * max_overlap_#). , " ".

input:
    [                        ] to fill
    [  (]  )  { ([}) ]  ( [) ]
return:
    Result set of squares which maximize cover, secondarily
     minimizing the size of the Result set if covered areas are equal

the score of the leftmost element is {area:100^2, num:1}
for each square S in order, left->right:
    (Assuming you pick S in Result...)
    let Candidates = {all squares which overlap S and are left of S}
                     + {first non-overlapping square left of S}
    for each candidate C:
        let score(S) = score(C) + {area:new_area_covered_by_S, num:1}
        pick candidate BestC which maximizes score(S)
        draw a line between S and BestC

Take the square with the best score, and work your way backwards
 along the chain of best-picks, returning only those squares.

, 0,0001%, " , , ". , .

, ( , ); .

, , , .

Answer 3

algorithmist.

.

, , -, , O (n ^ 2) .

, , , "", . , , "". - O (n ^ 2), O (n log (n)), .

#!/usr/bin/python

START_EVENT, END_EVENT = 0, 1  # handle starts before ends at same point

def max_future(cands):
  return max(cands, key=lambda c: (c[1], c)[1])

def cover_max_segment_min(intervals):
  events = []
  for interval in intervals:
    events.append((interval[0], START_EVENT, interval))
    events.append((interval[1], END_EVENT, interval))
  cands = []
  outputs = []
  alive = None
  # Handle events by 
  #   event time, 
  #   starts before ends, 
  #   longer endings before shorter endings
  events.sort(key=lambda x: (x[0], x[1], -x[2][1]))
  for k, event_type, interval in events:
    if event_type == START_EVENT:
        cands.append(interval)
    if event_type == END_EVENT:
        cands.remove(interval)
        if interval is alive:
            alive = None
    if not alive and cands:
        outputs.append(max_future(cands))
        alive = outputs[-1]
  return outputs

assert cover_max_segment_min([(0, 3), (1, 4), (3, 5)]) == \
   [(0, 3), (3, 5)]
assert cover_max_segment_min([(0, 3), (3, 5), (1, 4)]) == \
   [(0, 3), (3, 5)]
assert cover_max_segment_min([(0, 3)]) == [(0, 3)]
assert cover_max_segment_min([]) == []
assert cover_max_segment_min([(-10, 10), (1, 2), (3, 5)]) == [(-10, 10)]
assert cover_max_segment_min([(1, 2), (2, 3), (3, 4)]) == \
   [(1, 2), (2, 3), (3, 4)]
assert cover_max_segment_min([(1, 4), (1, 2), (3, 3)]) == \
   [(1, 4)]