Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

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

Authors James Koppel, Yun William Yu

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.17.pdf
  • Filesize: 2.88 MB
  • 20 pages

Document Identifiers

Author Details

James Koppel
  • Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA
Yun William Yu
  • Computer and Mathematical Sciences, University of Toronto at Scarborough, Canada
  • Department of Mathematics, University of Toronto, Canada

Funding

  • Yu, Yun William: This work is supported by faculty startup funds from UTSC.

Acknowledgements

The authors thank Aviv Adler and Quanquan Liu for comments on earlier drafts of this paper, and thank the members of the MIT Gymnastics team for fostering our love of gymnastics.

Cite AsGet BibTex

James Koppel and Yun William Yu. Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.17

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.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Problems, reductions and completeness
Keywords
  • complexity
  • games
  • sports

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. U.S. Figure Skating Scoring Guide. URL: https://usfigureskating.org/sites/default/files/media-files/Scoring%20Cheat%20Sheet.pdf.
  2. Element Symbols for Men’s Artistic Gymnastics, May 2015. URL: https://www.gymnastics.sport/publicdir/rules/files/en_MAG%20Element%20Symbols%20Booklet.pdf.
  3. FIS Freestyle Skiing Judging Handbook, October 2018. URL: https://assets.fis-ski.com/image/upload/v1540187845/fis-prod/Freestyle_Skiing_Judging_Handbook.pdf.
  4. Judges Handbook, Snowboard & Freeski, June 2019. URL: https://assets.fis-ski.com/image/upload/v1610953451/fis-prod/assets/FIS_SB_FK_JudgesHandbook_20_21.pdf.
  5. 2022 - 2024 Code of Points: Men’s Artistic Gymnastics, February 2020. URL: https://www.gymnastics.sport/publicdir/rules/files/en_MAG%20CoP%202022-2024.pdf.
  6. 2022 - 2024 Code of Points: Women’s Artistic Gymnastics, February 2020. URL: https://www.gymnastics.sport/publicdir/rules/files/en_WAG%20CoP%202022-2024.pdf.
  7. 2022 - 2024 Code of Points: Rhythmic Gymnastics, December 2021. URL: https://www.gymnastics.sport/publicdir/rules/files/en_2022-2024%20RG%20Code%20of%20Points.pdf.
  8. 2022 - 2024 Code of Points: Trampoline Gymnastics, May 2021. URL: https://www.gymnastics.sport/publicdir/rules/files/en_TRA%20CoP%202022-2024.pdf.
  9. Special Regulations & Technical Rules: Single & Pair Skating and Ice Dance, 2021, June 2021. URL: https://www.isu.org/figure-skating/rules/fsk-regulations-rules/file.
  10. Dressage Rules; 25th edition, effective 1st January 2014, January 2022. URL: https://inside.fei.org/sites/default/files/FEI_Dressage_Rules_2022_Clean_Version_V2.pdf.
  11. Aviv Adler, Jeffrey Bosboom, Erik D Demaine, Martin L Demaine, Quanquan C Liu, and Jayson Lynch. Tatamibari is NP-complete. arXiv preprint arXiv:2003.08331, 2020. Google Scholar
  12. Aviv Adler, Erik D Demaine, Adam Hesterberg, Quanquan Liu, and Mikhail Rudoy. Clickomania is Hard, Even With Two Colors and Columns. The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, 2:325, 2017. Google Scholar
  13. Greg Aloupis, Erik D Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games are (Computationally) Hard. Theoretical Computer Science, 586:135-160, 2015. Google Scholar
  14. Christina Backes, Jan Kuentzer, Hans-Peter Lenhof, Nicole Comtesse, and Eckart Meese. GraBCas: a Bioinformatics Tool for Score-Based Prediction of Caspase-and Granzyme B-Cleavage Sites in Protein Sequences. Nucleic Acids Research, 33(suppl_2):W208-W213, 2005. Google Scholar
  15. David W. Carmichael. File:2018 Winter Olympics - Yuzuru Hanyu FS (1).jpg. https://commons.wikimedia.org/wiki/File:2018_Winter_Olympics_-_Yuzuru_Hanyu_FS_(1).jpg, February 2018.
  16. Jan Christensen, Anders Nicolai Knudsen, and Kim S Larsen. Soccer is Harder than Football. International Journal of Foundations of Computer Science, 26(4):477-486, 2015. Google Scholar
  17. Erik D Demaine, Martin L Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, and Y William Yu. Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,... Journal of Information Processing, 25:515-527, 2017. Google Scholar
  18. Michael R Garey and David S Johnson. Computers and Intractability, volume 174. Freeman San Francisco, 1979. Google Scholar
  19. Olympics Gymnastics. Women’s Uneven Bars Final | Tokyo Replays. https://www.youtube.com/watch?v=I84it6P5_i8, October 2021.
  20. Ilgar Jafarov. File:Rhythmic gymnastics at the 2016 Summer Olympics, Marina Durunda 30.jpg. https://commons.wikimedia.org/wiki/File:Rhythmic_gymnastics_at_the_2016_Summer_Olympics,_Marina_Durunda_30.jpg, November 2016.
  21. Walter Kern and Daniël Paulusma. The New FIFA Rules are Hard: Complexity Aspects of Sports Competitions. Discrete Applied Mathematics, 108(3):317-323, 2001. Google Scholar
  22. Christina Marmet. What to Expect From the New Scoring System? URL: https://insidesynchro.org/2021/04/08/what-to-expect-from-the-new-scoring-system/.
  23. Javid Nikpour/Tasnimnews. Gymnastics at the 2016 Summer Olympics. https://www.tasnimnews.com/en/news/2016/08/12/1155951/gymnastics-at-the-2016-summer-olympics/photo/3, August 2016.
  24. James B Orlin. A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows. Mathematical Programming, 78(2):109-129, 1997. Google Scholar
  25. Duncan Rawlinson. Freestyle Skiing Men’s Aerials Final 19 . https://www.flickr.com/photos/44124400268@N01/4392687057, February 2010.
  26. Thomas J Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 216-226, 1978. Google Scholar
  27. Temple F Smith, Michael S Waterman, et al. Identification of Common Molecular Subsequences. Journal of Molecular Biology, 147(1):195-197, 1981. Google Scholar
  28. Masamichi Tsuboi. On the Melting Temperature of Nucleic Acid in Solution. Bulletin of the Chemical Society of Japan, 37(10):1514-1522, 1964. Google Scholar
  29. Sander van Ginkel. Rio 2016 Summers Olympics. https://flickr.com/photos/139991533@N04/28558139233, August 2016.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact