By multidimensional behavior, we mean the solution space of a linear constant-coefficient system of partial difference or differential equations. Within the behavioral framework, natural concept of interconnection has been introduced by J. C. Willems. The regular interconnection problem can be formulated as follows: Given behavior ( the plant), find-if possible-another behavior ( a controller) such that their interconnection is not redundant and is equal to certain desired behavior. We give constructive solution to this problem, which is in terms of polynomial matrix equations that can be solved using the theory of Grobner bases. We also study dual problem concerning the existence of direct sum decompositions of multidimensional behaviors. Finally, we present unified framework for studying both problems as special cases of constructing relative complements in the lattice of behaviors.