Luna Moon wrote:
> In a 2D array of double(floating point) numbers,
>
> ideally it should have an ordering on two dimensions:
>
> for left to right, the numbers should increase,
>
> from bottom to up, the numbers should increase,
>
> if in the middle of some row and some column, there are valleys and
> peaks, which means that the ordering is violated,
>
> I want to detect these violations and set the peaks or valleys to some
> predefined constants, say 1.
>
> my question is:
>
> how to do that efficiently in C/C++, also also Matlab?
[snip]
I don't think that this is really language dependent.
Note that not a single entry is in violation of the order but a pair of
adjacent (horizontally or vertically) entries (this raises the question,
where you want to put the 1).
The entries form a pattern like this:
xxxx
   
xxxx
   
xxxx
You can assign values to the entries so that there is exactly one violating
edge and you can even make it so that this edge can be anywhere. For this
reasin, just verifying that no violations happen requires inspection of all
horizontal and vertical edges in the pattern. The number of edges is
approximately twice the number of entries in the matrix. Therefore, no
algorithm can have better than linear (in the number of matrix entries)
runtime in the worst case. Thus, I would go with the simple, straight
forward implementation.
Best
KaiUwe Bux
