The complexity of the reconstruction of \((r,h,v)\) from two projections and an approximation algorithm (Q2755045)

This paper considers the problem of reconstructing a set of points in \(Z^2\) using only the horizontal and vertical projection: given two vectors \(R=(r_1, \dots ,r_n)\) and \(C=(c_1,\dots,c_n)\), \(r_i=\) the numbers of elements in row \(i\), \(c_k=\) the number of elements in column \(k\), find the object \(S\) with \(R\) and \(C\) as horizontal and vertical projection.NEWLINENEWLINENEWLINEThe object \(S\) very often will have given properties like connectiveness \((p)\), horizontal convexity \((h)\), vertical convexity \((v)\). In this article rectangular property \((r)\) is cousidered together with \((h)\) and \((v)\). NEWLINENEWLINENEWLINEThe consistency problem investigates whether there is such an object with given projections, the reconstruction problem constructs the required object \(S\). The main results are: NEWLINENEWLINENEWLINE1. \(\text{CONSISTENCY}_{(R,C)} (r,h,v)\) is \(NP\)-complete and \(NP\)-hard. NEWLINENEWLINENEWLINE2. \(\text{RECONSTRUCTION}_{(R,C)} (r,v)\) is \(NP\)-complete and \(NP\)-hard.NEWLINENEWLINENEWLINE3. \(\text{CONSISTENCY}_{(R,C)}(r)\) is \(NP\)-complete.NEWLINENEWLINENEWLINE4. \(\text{RECONSTRUCTION}_{(R,C)}(r)\) is \(NP\)-hard. NEWLINENEWLINENEWLINEAn algorithm for \(\text{RECONSTRUCTION}_{(R,C)}(r,h,v)\) is given and evaluated.