Reconstructing a three-dimensional model with arbitrary errors
Bonnie Berger, Jon M. Kleinberg, Tom Leighton · 1996
A number of current technologies allow for the determination of inter-atomic distance information three-dimensional structure?For the case of an n x n matrix in which every entry is specified, we provide a randomized algorithm running in time O(n log n) that enumerates all structures consistent wit h at most (~-s) n errors per row, with high probability y.In the case of randomly located errors, we can correct errors of the same density in a sparse matrix -one in which only a ,6 fraction of the entries in each row are given, for any constant ~>0.