Three-dimensional models of the spine are commonly used to diagnose, to treat, and to study spinal deformities. Creating these models is however time-consuming and, therefore, expensive. We propose in this paper a reconstruction method that finds the most likely 3D reconstruction given a maximal error bound on a limited set of landmark locations supplied by the user. This problem can be solved using second-order cone programming, leading to a globally convergent method that is considerably faster than currently available methods. A user can, with our current implementation, interactively modify the landmark locations and receive instantaneous feedback on the effect of those changes on the 3D reconstruction instead of blindly selecting landmarks. The proposed method was validated on a set of 53 patients who had adolescent idiopathic scoliosis using real and synthetic tests. Test results showed that the proposed method is considerably faster than currents methods (about forty times faster), is extremely flexible, and offers comparable accuracy.