License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.17
URN: urn:nbn:de:0030-drops-159877
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15987/
Go to the corresponding LIPIcs Volume Portal

Koppel, James ; Yu, Yun William

Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports

pdf-format:
LIPIcs-FUN-2022-17.pdf (3 MB)

Abstract

Some Olympic sports, like the marathon, are purely feats of human athleticism. But in others such as gymnastics, athletes channel their athleticism into a routine of skills. In these disciplines, designing the highest-scoring routine can be a challenging problem, because the routines are judged via a combination of artistic merit, which is largely subjective, and technical difficulty, which comes with complicated but objective scoring rules. Notably, since the 2006 Code of Points, FIG (International Gymnastics Federation) has sought to make gymnastics scoring more objective by encoding more of the score in those objective technical side of scoring, and in this paper, we show how that push is reflected in the computational complexity of routine optimization.
Here, we analyze the purely-technical component of the scoring rules of routines in 17 different events across 5 Olympic sports. We identify four attributes that classify the common rules found in scoring functions, and, for each combination of attributes, prove hardness results or provide algorithms for designing the highest-scoring routine according to the objective technical component of the scoring functions. Ultimately, we discover that optimal routine construction for events in artistic, rhythmic, and trampoline gymnastics is NP-hard, while optimal routine construction for all other sports is in P.

BibTeX - Entry

@InProceedings{koppel_et_al:LIPIcs.FUN.2022.17,
  author =	{Koppel, James and Yu, Yun William},
  title =	{{Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15987},
  URN =		{urn:nbn:de:0030-drops-159877},
  doi =		{10.4230/LIPIcs.FUN.2022.17},
  annote =	{Keywords: complexity, games, sports}
}

Keywords: complexity, games, sports
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI