The structure of a protein plays a pivotal role in determining its function. Often, the protein surface’s shape and curvature dictate its nature of interaction with other proteins and biomolecules. However, marked by corrugations and roughness, a protein’s surface representation poses significant challenges for its curvature-based characterization. In the present study, we employ unsupervised machine learning to segment the protein surface into patches. To measure the surface curvature of a patch, we present an algebraic sphere fitting method that is fast, accurate, and robust. Moreover, we use local curvatures to show the existence of “shape complementarity” in protein-protein, antigen-antibody, and protein-ligand interfaces. We believe that the current approach could help understand the relationship between protein structure and its biological function and can be used to find binding partners of a given protein.