Fast algorithms for minimum matrix norm with application in computer graphics

In this paper we consider the following problem. Given (r1,r2, ...,rn)∈ Rn, for anyI= (I1,I2,...,In)∈ Zn, letE1=(eij), whereeij=(ri−rj)−(Ii−Ij), findI ∈ Zn such that |EI| is minimized, where |·| is a matrix norm. This problem arises from optimal curve rasterization in computer graphics, where minimum distortion of curve dynamic context is sought. Until now, there has been no polynomial-time solution to this computer graphics problem. We present a very simpleO(n lgn)-time algorithm to solve this problem under various matrix norms.