Serh.kry's blog

Elimination of pairs of intersecting segments
By Serh.kry, history, 9 years ago, translation, In English

Here is the problem I'm trying to solve. Help me please to find a solution.

There are some segments that have start and end point on coordinate line. Each time we can eliminate one pair of intersecting segments.

The problem: how to maximize the count of eliminated segments?

Each time we removing one pair we might break another one. If one segment is intersecting several another segments, how to select the right one to eliminate as pair with former?

Example of elimination process:
8 segments was removed

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

up

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I'm not really sure about this, but can't we just sort all segments by their left ends? Then, starting from the first one, remove current segment and segment with left end closest to left end of our current segment and not bigger than right end of current segment (if such segment exists, of course). I can't prove this strictly, but intuitively it seems this way we can't affect any other pair of intersecting segments.

I would be glad if someone could give me counter example to this algorithm (or provide a proof)

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Here's what I think.

If we sort segments according to right end points, we can have sets with segments ending on the same point. Start from back(to understand better). The best chance a segment from the backmost set has of overlapping with a segment from previous sets is the longest segment in the back set. So, within a set, if there are even number of elements, they cancel out each other, and if odd number of elements, then all but one cancel out each other. Then, we get at most one segment from the back set. Similarly, find the 0/1 segment from all such sets.

The segments we have left will form some chains. A chain is a maximal group of consecutive segments such that the end of one segment overlaps with the next segment we got from the consecutive sets. In this case, we can remove all the segments from the chain if the chain length is even, or exatly one will remain(either first or last segment of the chain). So we greedily compute the chains.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

If I didn't miss anything, sort the endpoints of all segments (in case of a tie, assuming segments with equal endpoints intersect, put the beginnings first). Each time a segment start comes that segment becomes active, and when it ends it's no longer active. Now when a segment ends, pair it with the active segment that ends the soonest. If there's no active segment, that segment remains forever alone :c

In these problems greedy solutions usually work, but you have to be careful to pick the right one, as wrg0ababd's failed attempt shows.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Seems legit. Thank you very much. I'm thinking about keeping active segments in priority queue, where top segment ends first, so each time we can get closest-end segment with O(1) complexity. And here comes another problem that I've met some time ago.

    When segment ends, we need to make inactive at least this one segment and may be another one that intersects with former. If we store segments in the priority queue, we have linear time for deleting non-top element, so we can just mark as invalid those segments we are removing. In that case we will keep some invalid segments in queue, so we will waste some memory.

    Another approach is to use TreeSet that provides log(n) to take closest-end segment and also log(n) for removing. So we win some memory and lose some time.

    Are things I'm talking about are legit? May be there is much simpler approach?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • O(log n) is usually fast enough that it doesn't matter unless the time limit is really tight, so you should go for the simple solutions
      • Deleting from a priority queue is also O(log n), so you don't even get any complexity improvements from actually implementing your own priority queue.

      So just use the set.

      → Reply