Details
- Supervisors
- Faculty
- Degree label
- Abstract
- Competitive programming consists in the organization of programming contests, which see the world's most talented coders compete to solve problems of an algorithmic nature by implementing efficient programs as quickly as possible. Recently, geometry problems have had an increasing importance in those contests, but many contestants dislike them for being too technical or causing too precision issues linked to the use of floating-point numbers. We believe that those complaints are for the largest part due to a lack of specific training on the basics of computational geometry. We therefore introduce a new handbook of computational geometry, aimed primarily at the competitive programming public. It treats the subject in a practice-oriented way, providing code snippets for every operation, and explaining them in intuitive terms with the help of a large amount of illustrative figures. Its contents focus on the foundations of both 2D and 3D computational geometry, as well as the management of floating-point imprecisions, where we present a model of error propagation based on magnitude conditions and dimensionality of values. In addition, we present an original geometry contest whose problems showcase innovative notions and techniques, especially in 3D geometry. We hope that in the future, problem setters can reuse and adapt those ideas in order to foster variety and expand the scope of geometry as a competitive programming subfield.