Computational geometry on surfaces

Computational geometry grew into its own field over the past three decades, branching out of the study of how algorithms are designed and analysed. It examines geometric questions from a computing perspective and has drawn considerable research activity. Most of that work, however, assumes flat Euclidean space, either the plane or three-dimensional space, largely because those settings underpin the field's first applications and foundational results.

A few exceptions exist. Voronoi diagrams have been studied on the sphere, the cylinder, the cone and the torus, and many papers address triangulations on the sphere and other curved surfaces. These efforts were driven by practical questions in a widening range of disciplines, where real problems often take place on surfaces, with the sphere and the cylinder being the most frequent cases. Fields that encounter such problems include engineering, computer-aided design, manufacturing, geographic information systems, operations research, robotics, computer graphics and solid modelling.