This work is a generalization of the immersed interface method for discretization of a nondiagonal anisotropic Laplacian in 2D. This first-order discretization scheme enforces weakly diagonal dominance of the numerical scheme whenever possible. A necessary and sufficient condition depending on the mesh size h for the existence of this scheme at an interior grid point is found in terms of the anisotropy matrix. A linear programming approach is introduced for finding the weights of the schemes. The method is tested with a parametrized family of anisotropic Poisson equations. © 2004 Wiley Periodicals, Inc.