Minsegsumtwodim

Minsegsumtwodim

Just when I had posed "minsegsum" to my students, Jon Bentley's article [0] appeared in the CACM. The article mentioned the analogous problem in two dimensions and more or less suggested that it was a difficult one. As it mentioned no complexity results for the two-dimensional problem, both Jayadev Misra and I started to think about it and arrived independently at the same solution. Since the solution is complicated enough to present a problem of presentation, I decided to devote a note to it.

Remark about notation. By way of experiment I shall denote functional application by an infix period; it has the highest binding power of all operators and is (as usual) left-associative. By way of further experiment, I shall also use it for subscription. (End of Remark about notation.)

The functional specification for minsegsumwodim is

\begin{array}{l} I [ M, N: \mathrm {i n t} {M ≥ 1 ∧ N ≥ 1 } \ ; C (m, n: 0 ≤ m < M ∧ 0 ≤ n < N) \underline {{a r r a y}} o f ^ {p} i n t \ ; 1 [ x: i n t ] \ \end{array}

; m i n s e g s u m t w o d i m

\begin{array}{l} {R: x = (\min m 0, m 1, n 0, n 1: 0 ≤ m 0 ≤ m 1 ≤ M ∧ 0 ≤ n 0 ≤ n 1 ≤ N; \ (\underline {{\underline {{S}}}} m, n: m 0 ≤ m < m 1 ∧ n 0 ≤ n < n 1: (C. m. n)) } \ \end{array}

31

1

in which (as usual) the constants of the environ- ment are declared in the outer block.

To begin with we observe that $R ⇒ x ≤ 0$ since the summation may be over an empty range $(m0 = m1 \lor n0 = n1)$ . Furthermore we observe that $R$ is not changed if we change the range for $m0$ and $m1$ into $0 ≤ m0 < m1 ≤ M$ , since then the summation over the empty rectangle is still included. We adopt this change. (Condition $M ≥ 1$ has been chosen, rather than $M ≥ 0$ , to make this change permissible; $N ≥ 1$ has been chosen because, in general, our solution is most attractive for $N ≥ M$ .)

Our next step is to rewrite $\mathbb{R}$ in terms of nested MIN's. (At this stage the reader is invited to convince himself of the correctness of my rewriting and urged to shelve for the time being the question why $\mathbb{R}$ is rewritten this way.)

R: $x = \left( {M \downarrow N}\right. {m0} : 0 ≤ {m0} < M$ :

(MIN m1: m0<m1≤m:

(MIN n1: 0 ≤ n1 ≤ N: MS. m0. m1. n1 ))

M.S. m0. m1. n1 =

(MIN no: 0 ≤ n0 ≤ n1: (S n: no ≤ n < n1: Q.m0.m1.n))

Q.m0.m1.n = (∑m: m0≤m< m1: C.m.n)

Lines 2 through 4 of the above describe the linear minsegsum "in the n-direction" with mo and m1 as parameters: the m-direction has been

"pushed to the sides", i.e. to the outer minimiza- tions and the inner summation respectively.

We next derive -analogously to EWD897- two relations for ${MS}$ .

M S. m 0. m 1. 0 = 0 \tag {0}

and for $0 ≤ n < N$

\begin{array}{l} M S, m 0, m 1. (m 1 + 1) \ = {\mathrm {d e f i n i t i o n o f} M S } \ (\underline {{M I N}} n 0: 0 ≤ n 0 ≤ n 1 + 1: (\underline {{S}} n: n 0 ≤ n < n 1 + 1: Q. m 0. m 1. n)) \ = {\mathrm {F o r} n 0 = n 1 + 1, \mathrm {t h e s u m m a t i o n y i e l d s} 0 } \ (\min n 0: 0 ≤ n 0 ≤ n 1: (\sum n; n 0 ≤ n < n 1 + 1: Q, m 0, m 1, n)) \min 0 \ = {\mathrm {i s o l a t i o n o f l a s t t e r m o f s u m m a t i o n} } \ (\min n 0: 0 ≤ n 0 ≤ n 1: (\sum_ {n: n 0} ≤ n < n 1: Q, m 0, m 1, n) \ + Q. m 0. m 1. n 1) \min O \ = {Q. m 0. m 1. n 1 d o e s n o t d e p e n d o n n 0 a n d \ \end{array}

addition then distributes over minimization

((M _ {2} N n 0: 0 ≤ n 0 ≤ n 1: (\sum n: n 0 ≤ n < n 1: Q. m 0. m 1. n))

\begin{array}{l} + Q. m 0. m 1. n 1) \min 0 \ = {\mathrm {d e f i n i t i o n} \circledast M S } \ \end{array}

(M S. m 0. m 1. n 1 + Q. m 0. m 1. n 1) \min O \tag {1}

For $Q$ we derive (directly from its definition)

Q. m 0. m 0. n 1 = 0 \tag {2}

Q. m 0. (m 1 + 1). n 1 = Q. m 0. m 1. n 1 + C. m 1. n 1. (3)

Our rewritten R tells us that for any m0,m1 combination we have to find the minimum of MS.m0.m1.n1 for all n1, while (1) gives a recurrence relation for that sequence of values. The snag is that recurrence relation contains the term Q.m0.m1.n1, which -see (3)- satisfies a recurrence relation over m1. In order to exploit these two "orthogonal" recurrence relations to the fullest the program evaluates for each value of mo the M-mo recurrences (1) in synchrony. To this end a local array MSv(m: mo<m≤M) is introduced, such that whenever MSv.m1 is adjusted, its value changes from MS.m0.m1.n1 to MS.m0.m1.(n1+1). Furthermore a local scalar Qv is introduced such that whenever Qv is adjusted, its value changes from Q.m0.m1.n1 to Q.m0.(m1+1).

The annotated program is given below. In the initializaton of $x$ , $x ≤ 0$ is used; in its adjustment we use that min is associative.

Because we wish to use each MS-value as soon as it is computed, i.e. equals MS.m0.m1.(n1+n1), line 2 of the rewritten R is rewritten once more:

0 min (MIN n1: 0 ≤ n1 < N: MS. m0. m1. (n1 + 1)) , where the initial 0 can be taken out and taken care of by the initializaton.

\begin{array}{l} \left[ m 0: \mathrm {i n t} \right]; x := 0; m 0 := 0 \ ; \underline {{d o}} m 0 ≠ M \rightarrow \ \end{array}

I [ M S v (m: m 0 < m ≤ M) \mathrm {a r r a y} \mathrm {o f} \mathrm {i n t}

; m 1, n 1: i n t

; m 1 := m 0; \underline {{d o}} m 1 ≠ M \rightarrow m 1 := m 1 + 1; M S v. m 1 := 0 \underline {{o d}}

; n 1 := 0 \left{\left(\underset {m: m 0 < m} {\mathrm {A}} M: M 0 < m ≤ M: M S v. m = M S. m 0. m. n 1\right) \right}

; \underline {{d o}} n! ≠ N \rightarrow

[ [ Q v: i n t; Q v, m 1 := 0, m 0 {Q v = Q. m 0. m 1. n 1 }

; \underline {{d o}} m 1 ≠ M \rightarrow

Q v, m 1 := Q v + C. m 1. n 1, m 1 + 1

{Q v = Q. m 0. m 1. n 1 }

; M S v. m 1 := (M S v. m 1 + Q v) \min o

; X := X \min M S v. m 1

\overline {{o d}}

\vert 1; n 1 := n 1 + 1

\mathrm {o d}

] 1; m 0 := m 0 + 1

\overline {{o d}}

1

Side remark Eventually, we came up with a program that works for $M = 0 \vee N = 0$ as well. We could have made our analysis also applicable in that case by defining the minimum of an empty set as "big enough" -0,say-.(End of Side remark.)