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

## Contents

## 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]} - Rugby union (spatio-temporal visualisation)
^{[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

## References

- ↑ Okabe, A; Boots, B; Sugihara, K; Chui, S (2002).
*Spatial Tessellations Concepts and Applications of Voronoi Diagrams*. Chichester: Wiley. - ↑ 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. - ↑ 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. - ↑ Liebling, Thomas; Pournin, Lionel (2012). "Voronoi diagrams and Delaunay triangulations: Ubiquitous siamese twins".
*Documenta Mathematica***2012**: 419-431. - ↑ Okabe, Atsuyuki (1992).
*Spatial Tessellations*. Chichester: Wiley. - ↑ Liebling, Thomas; Pournin, Lionel (2012). "Voronoi diagrams and Delaunay triangulations: Ubiquitous siamese twins".
*Documenta Mathematica***2012**: 419. - ↑ 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. - ↑ Aurenhammer, Franz (1991)). "Voronoi diagrams—a survey of a fundamental geometric data structure".
*ACM Computing Surveys***23(3)**: 345. - ↑ Aurenhammer, Franz (1991). "Voronoi diagrams—a survey of a fundamental geometric data structure".
*ACM Computing Surveys***23(3)**: 345-404. - ↑ Zheng, Liping et al (2014). "Geometry-constrained crowd formation animation".
*Computers & Graphics***38**: 268-276. - ↑ Du, Qiang; Faber, Vance; Gunzburger, Max (1999). "Centroidal Voronoi Tessellations: Applications and Algorithms".
*SIAM Review***41(4)**: 637–676.. - ↑ 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. - ↑ 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**. - ↑ Horton, Michael; Gudmundsson, Joachim; Chawla, Sanjay; Estephan, Joel (2014). "Classification of passes in football matches using spatiotemporal data".
*arXiv***arXiv:1407.5093**. - ↑ Horton, Michael; Gudmundsson, Joachim; Chawla, Sanjay; Estephan, Joel (2015). "Automated classification of passing in football".
*Pacific-Asia Conference on Knowledge Discovery and Data Mining*. - ↑ 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*. - ↑ 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. - ↑ Sumpter, David (25 February 2017). "The geometry of attacking football". https://medium.com/@Soccermatics/the-geometry-of-attacking-football-bee87e7a749. Retrieved 23 March 2018.
- ↑ Bornn, Luke; Cervone, Dan; Fernandez, Javier (2018). "Soccer analytics".
*Significance***https://doi.org/10.1111/j.1740-9713.2018.01146.x**. - ↑ Aldridge, Colin et al (2002). "Spatio-temporal and object visualization in rugby union".
*Information Science Discussion Papers***2002(3)**: 1-22. - ↑ Burn-Murdoch, 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.
- ↑ 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**. - ↑ Kim, S (2004). "Voronoi analysis of a soccer game".
*Nonlinear Analysis: Modelling and Control***9(3)**: 233-240. - ↑ Fujimura, Akira; Sugihara, Kokichi (2005). "Geometric analysis and quantitative evaluation of sport teamwork".
*Systems and Computers in Japan***36(6)**: 49-58. - ↑ 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. - ↑ Monier, Emad; Wilhelm, Per; Ruckert, Ulrich (2009). "Template matching based tracking of players in indoor team sports".
*Distributed Smart Cameras*: 1-6. - ↑ Metulini, Rodolfo (2016). "Spatio-Temporal Movements in Team Sports: A Visualization approach using Motion Charts".
*arXiv***arXiv:1611.09158**. - ↑ 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*. - ↑ Mantovani, G; Ravaschio, P; Piaggi, P; Landi, A (2010). "Fine classification of complex motion pattern in fencing".
*Procedia Engineering***2(2)**: 3423-3428. - ↑ 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. - ↑ 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. - ↑ 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.
- ↑ 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. - ↑ Cervone, Dan (2015). "NBA Court Realty". Dan Cervone. http://dcervone.com/slides/court_realty.html#/. Retrieved 20 October 2017.
- ↑ Law, James (2005). "Analysis of multi-robot cooperation using Voronoi diagrams".
*Pace Pacing And Clinical Electrophysiology*. - ↑ Nakanishi, Ryota et al (2009). "An Approximate Computation of the Dominant Region Diagram for the Real-Time Analysis of Group Behaviors".
*RoboCup*. - ↑ 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.
- ↑ 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.
- ↑ Fujimura, Akira; Sugihara, Kokichi (2005). "Geometric analysis and quantitative evaluation of sport teamwork".
*Systems and Computers in Japan***36(6)**: 49-58. - ↑ 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. - ↑ 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**.