The rod-shaped bacterium Escherichia coli selects the cell center as site of division with the help of the proteins MinC, MinD, and MinE. This protein system collectively oscillates between the two cell poles by alternately binding to the membrane in one of the two cell halves. This dynamic behavior, which emerges from the interaction of the ATPase MinD and its activator MinE on the cell membrane, has become a paradigm for protein self-organization. Recently, it has been found that not only the binding of MinD to the membrane, but also interactions of MinE with the membrane contribute to Min-protein self-organization. Here, we show that by accounting for this finding in a computational model, we can comprehensively describe all observed Min-protein patterns in vivo and in vitro. Furthermore, by varying the system's geometry, our computations predict patterns that have not yet been reported. We confirm these predictions experimentally.