Self-organized complex structures in nature, e.g., viral capsids, hierarchical biopolymers, and bacterial flagella, offer efficiency, adaptability, robustness, and multi-functionality. Can we program the self-assembly of three-dimensional (3D) complex structures using simple building blocks, and reach similar or higher level of sophistication in engineered materials? Here we present an analytic theory for the self-assembly of polyhedral nanoparticles (NPs) based on their crystal structures in non-Euclidean space. We show that the unavoidable geometrical frustration of these particle shapes, combined with competing attractive and repulsive interparticle interactions, lead to controllable self-assembly of structures of complex order. Applying this theory to tetrahedral NPs, we find high-yield and enantiopure self-assembly of helicoidal ribbons, exhibiting qualitative agreement with experimental observations. We expect that this theory will offer a general framework for the self-assembly of simple polyhedral building blocks into rich complex morphologies with new material capabilities such as tunable optical activity, essential for multiple emerging technologies.