A three-dimensional memory device includes alternating stacks of electrically conductive strips and spacer strips located over a substrate and laterally spaced apart among one another by memory stack assemblies. The spacer strips may include air gap strips or insulating strips. Each of the memory stack assemblies includes two two-dimensional arrays of lateral protrusion regions. Each of the lateral protrusion regions comprises a respective curved charge storage element. The charge storage elements may be discrete elements located within a respective lateral protrusion region, or may be a portion of a charge storage material layer that extends vertically over multiple electrically conductive strips. Each of the memory stack assemblies may include two rows of vertical semiconductor channels that laterally overlie a respective vertical stack of charge storage elements.