A color filter array (CFA) used in a digital camera is a mosaic of spectrally selective filters, which allows only one color component to be sensed at each pixel. The missing two components of each pixel have to be estimated by methods known as demo- saicking. The demosaicking algorithm and the CFA design are cru- cial for the quality of the output images. In this paper, we present a CFA design methodology in the frequency domain. The frequency structure, which is shown to be just the symbolic DFT of the CFA pattern (one period of the CFA), is introduced to represent im- ages sampled with any rectangular CFAs in the frequency domain. Based on the frequency structure, the CFA design involves the solu- tion of a constrained optimization problem that aims at minimizing the demosaicking error. To decrease the number of parameters and speed up the parameter searching, the optimization problem is re- formulated as the selection of geometric points on the boundary of a convex polygon or the surface of a convex polyhedron. Using our methodology, several new CFA patterns are found, which out- perform the currently commercialized and published ones. Exper- iments demonstrate the effectiveness of our CFA design method- ology and the superiority of our new CFA patterns.