find the maximum possible length of segments (a scan line algorithm)

user_14744034 0
Viewed 59

The segments (their beginnings) are given. Let them be: 1, 4, 6, 9, 10. All segments have the same length C. We need to find such a maximum length (C) that there is no such common point that belongs to N segments. For example, if N = 2, and the length of the segments above is 4 (C = 4), then if we sort the coordinates of the beginning of the segments and their ends, we get: [1, 5], [4, 8], [6, 10], [9, 13], [10, 14] (it is not difficult to notice that at point 10 ([6, 10], [9, 13], [10, 14]) we have 3 segments intersecting at once, which contradicts the condition)

I know the algorithm for fixed ends of segments, but I do not know how to choose such ends so that the common point contains no more than N without O(n^2) iterations. Please help me

algorithm
1 Answers

Here's an O(n) time complexity algorithm, provided the beginnings of the segments are already sorted. The space complexity is O(1).

Let's define what a shared point means in terms of the absolute distances between the segment beginnings.

segment beginnings = [1,_,_,4,_,_,_,8] # empty cells added for illustration
N = 2
if we take C = 5 we get [1,_,_,4,_,_,_,8]
                           1,2,3,4,5
It's evident that there is shared point. If we had C = 4,
this wouldn't be the case since the end points of the segments don't count.

So, we can state that for 2 segments to have at least one shared point, the length of C must be at least abs(s_seg2 - s_seg1) + 2. This is the distance of the segment starts plus 2. This also means that C = abs(s_seg2 - s_seg1) + 1 avoids any common point between seg1 and seg2

Now, the above implies that to avoid one shared point between any 2 segments (N = 2), C must be min(abs(s_segi - s_segj))+1 for 0 <= i < len(segment_starts)-1, j = i+1.

How do we generalize this idea to one shared point between 3 segments (N = 3) or any number of segments with 2 <= N <= len(segment_starts)?

For 3 adjacent segments, s_seg1, s_seg2, s_seg3 to produce one shared point between the 3, the length of C must be abs(s_seg3 - s_seg1)+2, so +1 would be the maximum possible length of C.

The above motivates the following algorithm:

  1. Create a sliding window or 2 pointers with left = 0 and right = N-1. You could also say a sliding window of length N.
  2. Keep track of the minimum value of segment_starts[right] - segment_starts[left].
  3. Run a loop while right < len(segment_starts) and increment left and right after each iteration.
  4. At the end of the loop return the found min value + 1.

In pseudo code:

# assuming segment_starts is sorted none-decreasing

if N > len(segment_starts): return Infinity
if N < 2: raise Invalid Input Error

left, right = 0, N-1
curr_best = segment_starts[right] - segment_starts[left]
for right < len(segment_starts):
  curr_best = min(curr_best, segment_starts[right] - segment_starts[left])

return curr_best+1
user_77556650
Related