Minimum Common Region

Hello Matlab Users I want to find the minimum region that is common between ranges of closed intervals; and also the associated frequency. For example: 100 200 120 300 140 220 250 350 should return: 140 200; freq. = 3 250 300; freq. = 2

Is there any solution for this problem that is not largely dependant on for-loops? I appreciate your help.

Regards, NF

Answer 1

[Image Analyst]

What are your ranges? Is it 100-200, 120-300, 140-220, and 250-300? If so, there is no range that overlaps all those ranges. This is the code I used, which would work except that your 250-300 range doesn't overlap any of the prior 3 ranges:

ranges = [100 200 120 300 140 220 250 350];

% Reshape the array to put the low ends in column 1
% and the high ends in columns 2
ranges = [ranges(1:2:end); ranges(2:2:end)]'
% Get the low end of the overlapping region
lowEnd = max(ranges(:, 1))
% Get the high end of the overlapping region
highEnd = min(ranges(:, 2))

if highEnd < lowEnd
    msgbox('There is no overlap range');
end

I also didn't understand what this means: "freq. = 3 250 300; freq. = 2" Makes no sense whatsoever to me. Please explain.

Answer 2

[Noushin Farnoud]

 Thanks for your reply. I apologize for the confusion as I did not use the 'code mode' when I wrote this. Here's what I meant:
  A= [100 200;
120 300; 
140 220; 
250 350];

The minimum overlap is also all possible overlaps in this data set. In this example, the first 3 ranges overlap at 140-200 (with frequency = 3); and the 2nd and 4th ranges also overlap at 250-300 (frequency=2). Thanks

[Image Analyst]

I don't know how to do it without for loops, but that should not be a problem unless your array is millions of rows long. You could just have three nested for loops. In the second loop (but outside the innermost third loop), have Walter's code. For every row in A, check how B (a different row in A) overlaps it. Then increment your histogram (what you call freq). The thing that will take long is that for any given A and B (say you compared row 3 with row 9) you have a possible overlap. Now you have to check ALL the other rows (1 through N EXCEPT for 3 and 9) to see if they contain the same range - that would be the innermost third loop. Be careful to avoid double counting (for example checking row 3 against row 9 and then later row 9 against row 3 otherwise you'll get double counting) - I assume you can figure out how to avoid that. What use is this strange procedure for anyway?

Answer 3

[Walter Roberson]

If you have two closed intervals A and B, each a min/max pair, the region in common between them is

oint = [max(A(1),B(1)), min(A(2),B(2))];
if oint(2) < oint(1); oint = []; end

The operation is transitive: overlap(overlap(A,B),C) = overlap(A,overlap(B,C))

The operation is also commutative: overlap(A,B) = overlap(B,A)

[Walter Roberson]

Vectoring, taking advantage of the oddity that min(nan,Value) is Value and max(nan,Value) is Value:

oint = [max(A(:,1), B(:,1)), min(A(:,2), B(:,2))];

idx = oint(:,2) < oint(:,1);

oint(idx, :) = nan;