LEFTMOST ONE COMPUTATION ON MESHES WITH ROW BROADCASTING

Given a matrix of size square-root n X square-root n with every entry being a 0 or a 1, the leftmost-one problem asks to determine the posit ion of the leftmost 1, if any, in each row of the matrix. The leftmost -one problem finds applications in image processing, digitized geometr y and computer graphics, among others. Recently, an O(n1/6) time solut ion to the leftmost-one problem on a mesh with row buses has been prop osed. However, the computational model assumes that processors have un bounded memory. We show that the problem can be solved in O(n1/6) time on a square-root n X square-root n mesh with row broadcasting, even i f each processor has only a constant number of registers.