Return to Question

Given a integer value $n$, we generate a $n^2 \times n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning ceil as skyline point if you may.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?

Given a integer value $n$, we generate a $n^2 \times n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning points as skyline points if you may. $M[n^2,n^2]$ is a special turning point.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?

Given a integer value $n$, we generate a $n^2 * n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning ceil as skyline point if you may.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?

Given a integer value $n$, we generate a $n^2 \times n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning ceil as skyline point if you may.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?

Given a integer value n, we generate a n^2 x n^2 integer matrix M in the following way.

1. Each ceil has value range [1~n]
2. In each row, the value is nondecreasing. E.g. M[i, j] <= M[i, j+1]
3. In each column, the value is nondecreasing. E.g. M[i, j] <= M[i+1, j]

For example the following is a example of n=2 4x4 matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point (i,j) as

1. M[i,j] = M[i, j+1] - 1

2. M[i,j] = M[i+1, j] - 1

We can treat turning ceil as skyline point if you may.

For the above example, the turning points are (2,3) and (4,4).

We want to calculate the upper bound of total number of turning points, we denoted by |P|.

It is easy to proof that the upper bound size of set P is O(n^3).

However, the real data shows that |P| is always failing in the complexity of n^2 range.

Is there a way to proof that the upper bound of |P| is n^2?

Given a integer value $n$, we generate a $n^2 * n^2$ integer matrix $M$ in the following way.

1. Each ceil has value range $[1~n]$
2. In each row, the value is nondecreasing. E.g. $M[i, j] \leq M[i, j+1]$
3. In each column, the value is nondecreasing. E.g. $M[i, j] \leq M[i+1, j]$

For example the following is a example of $n=2$ & $4*4$ matrix.

1 1 1 2

1 1 1 2

2 2 2 2

2 2 2 2

We define the concept of turning point $(i,j)$ as

1. $M[i,j] = M[i, j+1] - 1$

2. $M[i,j] = M[i+1, j] - 1$

We can treat turning ceil as skyline point if you may.

For the above example, the turning points are $(2,3)$ and $(4,4)$.

We want to calculate the upper bound of total number of turning points, we denoted by $|P|$.

It is easy to proof that the upper bound size of set P is $O(n^3)$.

However, the real data shows that $|P|$ is always failing in the complexity of $n^2$ range.

Is there a way to proof that the upper bound of $|P|$ is $n^2$?