Sport Informatics and Analytics/Audiences and Messages/Visualising Data/Voronoi

From WikiEducator
Jump to: navigation, search
20 points and their Voronoi cells.

Introduction

Theme 4 of this course is Audiences and Messages. In our discussion of the visualisation of data aspects of the theme, we noted "At some point in the sport analytics process we share our findings with an audience".

This page introduces one form of visualising and sharing data, namely, a Voronoi diagram[1].

Adrienne Kemp describes the features of a Voronoi diagram:

Given a set of n points in m-dimensional Euclidean space, a Voronoi diagram partitions the space into n convex polygons, each containing one of the points, in such a way that all locations within the polygon are closer to that point than to any other.[2]

The name of the diagram comes from the mathematician, Georgy Voronoi, who defined it in a paper published in 1908[3]. There is a copy of the original paper, in French, in the Gottinger Digitalisierungszentrum archive.

In addition to Georgy Voronoi's paper, you can find a great deal of information about pre-Voronoi use of diagrams (including by Johannes Kepler and Rene Descarte) in Thomas Liebling and Lionel Pournin's (2012) paper[4].

You might also see reference to a Voronoi tessellation[5] in the literature. In this case the word 'tessellation' is synonomous with 'diagram'.

Definition

Thomas Lieling and Lionel Fournin note:

A Voronoi diagram induced by a finite set A of sites is a decomposition of the plane into possibly unbounded (convex) polygons called Voronoi regions, each consisting of those points at least as close to some particular site as to the others.[6]

These Voronoi regions change continuously over time and in sport reflect the dynamic nature of team play and spatial configuration[7].

Franz Aurenhammer states a Voronoi diagram:

... divides the plane according to the nearest-neighbour rule: Each point is associated with the region of the plane closest to it.[8]

Franz's paper[9] provides a most comprehensive computational geometry account of Voronoi diagrams and shares an extensive bibliography. If you have a particular interest in mathematics, we recommend Franz's paper to you. The original mathematics conventions are contained in Gregory Voronoi's 1908 paper.

The literature also makes mention of a centroidal Voronoi tessellation 38 (2014): 268-276.[10]. Qiang Du, Vance Faber and Max Gunzburger point out that a centroid Voronoi tesselation is:

a Voronoi tessellation whose generating points are the centroids (centers of mass) of the corresponding Voronoi regions.[11]

Voronoi diagrams in sport

Voronoi diagrams have attracted the attention of researchers in sport. Examples include:

  • Association football (motion analysis)[12], (passing networks and player movement dynamics)[13], (classification of passes)[14][15], (measuring tactical success)[16], (changes in space control)[17][18][19] (probabilistic movement models)[20], (player identification for transfers)[21](spatial dynamics)[22]
  • Football computer game (accurate measurement of player position)[23]
  • Field hockey (evaluating teamwork)[24]
  • Indoor sports (basketball, handball, squash)[25], (basketball)[26][27], (handball)[28]
  • Fencing (classification of complex motion patterns)[29]
  • Futsal (to identify and investigate the spatial dynamics of players’ behavior)[30][31]
  • Basketball (rebounding)[32], (tactical behaviour)[33], (NBA court realty)[34]
  • RoboCup Football (cooperation)[35], (group behaviour)[36], (tactical decision making)[37]
  • Netball[38]

Spatio-temporal location of players

Icon reading line.svg
How do we locate players to analyse performance?

One of the challenges researchers face when they try to track players' behaviours is to know, with reasonable accuracy, where players are in constantly changing configurations of players. To explore how some researchers have addressed this problem, we recommend you have a look at three papers that make an explicit attempt to explain their location methodologies. The first is a paper written in 2005 by Akira Fujimura and Kokichi Sugihara[39] that explains how they came to calibrate their Voronoi regions for the analysis of field hockey. The second is a paper that seeks to measure the centroid position of players in a game of football. Wouter Frencken[40] and his colleagues point out that in their study the centroid is the average position of the outfield players. Their methodology included the use of a local position measurement system. The third paper is a critique of Voronoi diagrams by Ulf Brefeld, Jan Lasek and Sebastian Mair (2018).[41]

What insights can you gain about how we measure and visualise location in team sports from these papers?



References

  1. ↑ Okabe, A; Boots, B; Sugihara, K; Chui, S (2002). Spatial Tessellations Concepts and Applications of Voronoi Diagrams. Chichester: Wiley.
  2. ↑ Kemp, Adrienne (2002). "Reviewed Work: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams". Journal of the Royal Statistical Society Series D (The Statistician) 51(3): 427-428.
  3. ↑ Voronoi, Georgy (1908). "Nouvelles applications des paramètres continus à la théorie de formes quadratiques". Journal für die reine und angewandte Mathematik 134: 198–287.
  4. ↑ Liebling, Thomas; Pournin, Lionel (2012). "Voronoi diagrams and Delaunay triangulations: Ubiquitous siamese twins". Documenta Mathematica 2012: 419-431.
  5. ↑ Okabe, Atsuyuki (1992). Spatial Tessellations. Chichester: Wiley.
  6. ↑ Liebling, Thomas; Pournin, Lionel (2012). "Voronoi diagrams and Delaunay triangulations: Ubiquitous siamese twins". Documenta Mathematica 2012: 419.
  7. ↑ Fonseca, Sofia; Diniz, Ana; Araujo, Duarte (2014). "Chapter 7: The measurement of space and time in evolving sport phenomena". In Davids, Keith et al. Complex Systemsin Sport. Book Publishers Routledge. pp. 125–144.
  8. ↑ Aurenhammer, Franz (1991)). "Voronoi diagrams—a survey of a fundamental geometric data structure". ACM Computing Surveys 23(3): 345.
  9. ↑ Aurenhammer, Franz (1991). "Voronoi diagrams—a survey of a fundamental geometric data structure". ACM Computing Surveys 23(3): 345-404.
  10. ↑ Zheng, Liping et al (2014). "Geometry-constrained crowd formation animation". Computers & Graphics 38: 268-276.
  11. ↑ Du, Qiang; Faber, Vance; Gunzburger, Max (1999). "Centroidal Voronoi Tessellations: Applications and Algorithms". SIAM Review 41(4): 637–676..
  12. ↑ Taki, Tsuyoshi; Hasegawa, Jun-ichi; Fukumura, Teruo (1996). "Development of motion analysis system for quantitative evaluation of teamwork in soccer games". Image Processing Proceedings 3: 815-818.
  13. ↑ Goncalves, Bruno et al (2017). "Exploring Team Passing Networks and Player Movement Dynamics in Youth Association Football". PLOS One https://doi.org/10.1371/journal.pone.0171156.
  14. ↑ Horton, Michael; Gudmundsson, Joachim; Chawla, Sanjay; Estephan, Joel (2014). "Classification of passes in football matches using spatiotemporal data". arXiv arXiv:1407.5093.
  15. ↑ Horton, Michael; Gudmundsson, Joachim; Chawla, Sanjay; Estephan, Joel (2015). "Automated classification of passing in football". Pacific-Asia Conference on Knowledge Discovery and Data Mining.
  16. ↑ Perl, Jürgen; Memmert, Daniel (2016). "Soccer analyses by means of artificial neural networks, automatic pass recognition and Voronoi-cells: An approach of measuring tactical success". Proceedings of the 10th International Symposium on Computer Science in Sports.
  17. ↑ Rein, Robert; Raabe, Dominik; Perl, Jürgen; Memmert, Daniel (2016). "Evaluation of changes in space control due to passing behavior in elite soccer using Voronoi-cells". Proceedings of the 10th International Symposium on Computer Science in Sports: 179-183.
  18. ↑ Sumpter, David (25 February 2017). "The geometry of attacking football". https://medium.com/@Soccermatics/the-geometry-of-attacking-football-bee87e7a749. Retrieved 23 March 2018.
  19. ↑ Bornn, Luke; Cervone, Dan; Fernandez, Javier (2018). "Soccer analytics". Significance https://doi.org/10.1111/j.1740-9713.2018.01146.x.
  20. ↑ Aldridge, Colin et al (2002). "Spatio-temporal and object visualization in rugby union". Information Science Discussion Papers 2002(3): 1-22.
  21. ↑ Burn-Murdoch, first=John (1 November 2018). "How data analysis helps football clubs make better signings". https://www.ft.com/content/84aa8b5e-c1a9-11e8-84cd-9e601db069b8. Retrieved 2 November 2018.
  22. ↑ Travassos, Bruno et al. "Practice task design in team sports: Representativeness enhanced by increasing opportunities for action". Journal of Sports Sciences https://www.tandfonline.com/doi/abs/10.1080/02640414.2012.712716.
  23. ↑ Kim, S (2004). "Voronoi analysis of a soccer game". Nonlinear Analysis: Modelling and Control 9(3): 233-240.
  24. ↑ Fujimura, Akira; Sugihara, Kokichi (2005). "Geometric analysis and quantitative evaluation of sport teamwork". Systems and Computers in Japan 36(6): 49-58.
  25. ↑ Kristan, Matej; Perš, Janez; Perše, Matej; Kovačič, Stanislav (2009). "Closed-world tracking of multiple interacting targets for indoor-sports applications". Computer Vision and Image Understanding 113(5): 598-611.
  26. ↑ Monier, Emad; Wilhelm, Per; Ruckert, Ulrich (2009). "Template matching based tracking of players in indoor team sports". Distributed Smart Cameras: 1-6.
  27. ↑ Metulini, Rodolfo (2016). "Spatio-Temporal Movements in Team Sports: A Visualization approach using Motion Charts". arXiv arXiv:1611.09158.
  28. ↑ Lopes, Antonio (2013). "Tracking Multiple Handball Players using Multi-Commodity Network Flow for Assessing Tactical Behavior". Scientific Conference Women and Handball: Scientific and Practical Approaches.
  29. ↑ Mantovani, G; Ravaschio, P; Piaggi, P; Landi, A (2010). "Fine classification of complex motion pattern in fencing". Procedia Engineering 2(2): 3423-3428.
  30. ↑ Fonseca, Sofia; Milho, João; Travassos, Bruno; Araújo, Duarte (2012). "Spatial dynamics of team sports exposed by Voronoi diagrams". Human movement science 31(6): 1652-1659.
  31. ↑ Fonseca, Sofia; Milho, João; Travassos, Bruno; Araújo, Duarte; Lopes, António (2013). "Measuring spatial interaction behavior in team sports using superimposed Voronoi diagrams". International journal of performance analysis in sport 13(1): 179-189.
  32. ↑ Maheswaran, Rajiv et al (March, 2014). "The Three Dimensions of Rebounding". http://www.sloansportsconference.com/wp-content/uploads/2014/02/2014_SSAC_The-Three-Dimensions-Of-Rebounding.pdf. Retrieved 20 October 2017.
  33. ↑ Lopes, Antonio et al (2015). "Using Voronoi diagrams to describe tactical behaviour in invasive team sports: an application in basketball". Cuadernos de Psicología del Deporte 15(1): 123-130.
  34. ↑ Cervone, Dan (2015). "NBA Court Realty". Dan Cervone. http://dcervone.com/slides/court_realty.html#/. Retrieved 20 October 2017.
  35. ↑ Law, James (2005). "Analysis of multi-robot cooperation using Voronoi diagrams". Pace Pacing And Clinical Electrophysiology.
  36. ↑ Nakanishi, Ryota et al (2009). "An Approximate Computation of the Dominant Region Diagram for the Real-Time Analysis of Group Behaviors". RoboCup.
  37. ↑ Prokopenko, Mikhail; Wang, Peter; Obst, Oliver (2014). "Gliders2014: Dynamic Tactics with Voronoi Diagrams". http://www.prokopenko.net/Publications/Agents/TDP_Gliders2014.pdf. Retrieved 20 October 2017.
  38. ↑ Werner, Joel; Webb, Jonathan (5 October 2017). "Shoal attack: How a school of fish helped Aussie netballers win gold". News. http://www.abc.net.au/news/2017-10-05/australian-netballs-secret-weapon-is-a-school-of-fish/9014326. Retrieved 20 October 2017.
  39. ↑ Fujimura, Akira; Sugihara, Kokichi (2005). "Geometric analysis and quantitative evaluation of sport teamwork". Systems and Computers in Japan 36(6): 49-58.
  40. ↑ Frencken, Wouter et al (2011). "Oscillations of centroid position and surface area of soccer teams in small-sided games". European Journal of Sport Science 11(4): 215-223.
  41. ↑ Brefeld, Ulf; Lasek, Jan; Mair, Sebastian (2018). "Probabilistic movement models and zones of control". Machine Learning https://doi.org/10.1007/s10994-018-5725-1.
Retrieved from "https://wikieducator.org/index.php?title=Sport_Informatics_and_Analytics/Audiences_and_Messages/Visualising_Data/Voronoi&oldid=1075095"