We study the problem of efficiently correcting an erroneous product of two \(n\times n\) matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in \({\tilde{O}}(n^2+kn)\) time and a deterministic \({\tilde{O}}(kn^2)\)-time algorithm for this problem (where the notation \({\tilde{O}}\) suppresses polylogarithmic terms in n and k).
Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked (unimodal) curve y =φ(x) minimizing the L2-distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of unimodal pieces under the condition that each unimodal piece is within a fixed L2-distance from the corresponding portion of f.
This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in &Ogr;(m4n &lgr;16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and &lgr;16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in &Ogr;(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of &kgr; rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for &kgr;n points is shown to be &Ogr;(n2) and &Ogr;(n3&kgr;4 log* &kgr;) for &kgr; = 2, 3 and &kgr; ≥ 4, respectively. Several related problems are also treated in a unified way.