The aim of this proposal is explore hardness results in the fields of Geometry Processing and Computer Graphics. Traditionally, research in Geometry Processing has concentrated on devising efficient methods for tasks such as shape segmentation, shape matching, reconstruction and analysis of geometric data among others. Unfortunately, the majority of existing techniques are presented in an ad-hoc manner demonstrating their performance only on a handful of examples, and often contain many ad-hoc steps and implicit human intervention. On the other hand, there has been very little systematic study of theoretical hardness of the problems in geometry processing and very few rigorous results exist on the theoretical limitations (i.e. impossibility) of methods that aim to solve problems in Geometry Processing and Computer Graphics. Having such results will not only shed light on the quality of performance of existing methods but also show why and when external (e.g. human) input is sometimes theoretically necessary. The goal of this proposal is to initiate a field-wide study of the inherent difficulty of geometric problems and to establish rigorous impossibility results. This can have an far-reaching impact in fields as diverse as medial imaging and protein structure analysis among many others.