Using GeoGebra and 3D printing for introducing Voronoi diagrams in school

Year: 2019 Authors: Edith Lindenbauer; Sandra Reichenberger; Tomasz Kaim; Michael Lewicki; Philipp Rittberger; Daniel Taubinger; Tobias Wösenböck; Michelle Zauner

Core claim

Voronoi diagrams can be taught effectively in school through interactive GeoGebra tasks, manual construction, natural pattern analysis, and 3D-printable design.

Topics

Voronoi diagrams, GeoGebra activities, 3D printing, school workshop

Domains

computational geometry, plane partitions, perpendicular bisectors, convex polygons, 3D design, architectural form, creative patterning, artistic applications

Methods

lesson plan, guided inquiry, hand construction, GeoGebra modeling, Tinkercad design

Media

GeoGebra applets, hand-drawn diagrams, nature photographs, 3D printed eggcup

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2019 Conference Proceedings

Using GeoGebra and 3D printing for introducing Voronoi diagrams in school

Edith Lindenbauer¹, Sandra Reichenberger² and Tomasz Kaim³, Michael Lewicki³, Philipp Rittberger³, Daniel Taubinger³, Tobias Wösenböck³, Michelle Zauner³

¹University College of Education Upper Austria, Austria; edith.lindenbauer@ph-ooe.at ²Johannes Kepler University Linz, Austria; sandreich@gmail.com ³Gymnasium und ORG Dachsberg, Austria

Abstract

In this workshop, a lesson plan designed for and already implemented in school will be carried out. The participants encounter Voronoi diagrams using GeoGebra but also constructing them by hand. After a brief theoretical introduction, they can examine Voronoi patterns in nature. Finally, we provide the option to design individual objects for everyday life applying knowledge about such patterns.

Introduction

In Austria, Voronoi diagrams are not part of the mathematics curriculum and thus usually not discussed in school. However, this topic offers a range of various possibilities for use in mathematics lessons, especially because the basic mathematical knowledge of Voronoi diagrams is part of the curriculum of lower secondary education. For these reasons, we decided to design a lesson plan for students with several real-world applications including interactive GeoGebra materials and 3D printing.

Mathematical Background

In the 19th century, Voronoi and Dirichlet first examined Voronoi diagrams [9]. Voronoi diagrams can be utilized in various contexts, for example, in civics and planning (e.g., solving location problems), in biology, chemistry, physics, climate research and economics [1]. Approximate Voronoi diagrams exist also in nature: the veins in dragonfly wings form (almost) a Voronoi diagram. This is probably beneficial for optimizing the supply of nutrients or elasticity [6]. Finally, this geometrical pattern can be exploited in various creative ways as presented in recent Bridges conferences, for instance, artistic applications in quilts [2] or applications in arts, furnishing, jewelry, architecture and design [4].

Let $S=\{P_1,P_2,\dots ,P_n\}$ be a finite set of points in ${\mathbb{R}}^2$. The points $P_i$ are called Voronoi points or sites. For every point $P_i$, the Voronoi region (or Voronoi cell) of $P_i$, which we denote by $V(P_i)$, is the set of points of ${\mathbb{R}}^2$ that are closer to $P_i$ than to any other point $P_j$ (or at most have the same distance):

The partition of ${\mathbb{R}}^2$ into Voronoi regions is called Voronoi diagram of S, denoted by V(S). The Voronoi region of a certain point $P_i$ includes all points in ${\mathbb{R}}^2$ that are nearer to $P_i$ than any other site. In ${\mathbb{R}}^2$, each Voronoi region is a convex polygon [9].

The inverse question – how to turn a convex partition of the plane into a Voronoi diagram by determining the Voronoi sites – proves to be more complicated. It is impossible to represent every convex partition as a Voronoi diagram, but if there exists a solution, in general the set of sites $P_i$ is not unique [3, 8].

Lindenbauer and Reichenberger

Workshop Description

In the following section, we describe a lesson plan for students for grade 6 or older, which also serves as the structure for the workshop at the conference. For implementing this lesson in school, it is important that the students already know perpendicular bisectors and their properties.

Task 1: From which post office do I get my parcel? - Introducing the problem

We start the workshop with the two GeoGebra applets “From which post office do I get my parcel?” (Figure 1). The participants should solve the following problem for three respectively for five points without knowing something about Voronoi diagrams.

Problem: In Linz, five post offices (yellow dots on the map) are going to open. Each house should be supplied by the nearest post office as the crow flies. Try to construct the delivery areas for each post office!

Figure 1: Applets: From which post office do I get my parcel? (https://www.geogebra.org/m/hrwkh3ke, https://www.geogebra.org/m/g8rmcq7z)

For solving the problem, the participants have to construct perpendicular bisectors of connecting lines amongst the given points. After constructing the Voronoi diagram the students should get time to reflect on some questions about the mathematical idea (e.g. Why do you draw perpendicular bisectors? How many have to be drawn?).

Afterwards, the participants can work on another real-world application of Voronoi with the GeoGebra applet “Lineup of a soccerteam” (Figure 2). In Task a, they have to construct one region of a Voronoi diagram. In Task b, the participants can model their own lineup for the soccer team for 11 or 10 players.

Problem a: You can see the lineup of a soccerteam. Construct the area, where the distance from the marked player to the ball is shorter than the distance from each other player to the ball. When should the marked player run to the ball?

Problem b: You are a trainer of a soccerteam. Now you have to decide the lineup of your team for the next match (4-3-3, 4-4-2, 4-1-4-1, …). Which strategy would you prefer? One of the players is excluded from the match. Now there are only 10 players on the pitch. What are you doing now?

Figure 2: Applet: Lineup of a soccerteam (https://www.geogebra.org/m/t7uh5WCM)

Using GeoGebra and 3D Printing for Introducing Voronoi Diagrams in School

Task 2: What is a Voronoi diagram? - Theoretical input

During the next step, we discuss the following definition of a Voronoi diagram with the participants:

The Voronoi region of a point $\mathrm{P}$ - called site or generator - is the set of all points in the plane that are closer to $\mathrm{P}$ than any other site. The set of all Voronoi regions is called Voronoi diagram.

First, we draw the Voronoi diagram for two points followed by creating the Voronoi region of one out of several points (Figure 3).

Figure 3: Creating Voronoi diagrams

For examining Voronoi diagrams and their mathematical properties in more detail, a further applet (see https://www.geogebra.org/m/jjnrsqsy) provides several tasks and questions (e.g., analyzing symmetries of diagrams) [7].

Generating Voronoi diagrams takes seconds on the computer, but drawing one manually by hand is a good way for a better understanding of the theory behind the patterns and promoting creativity (Figure 4).

Figure 4: Hand-drawn Voronoi diagrams

Task 3: Is it a Voronoi diagram? - Modelling with GeoGebra

There are several structures found in nature which seem to be Voronoi diagrams (e.g., wings of a dragonfly, honeycomb structure, carapace of a turtle) outlined in different publications [1, 6]. However, if someone wants to examine these structures, he or she can model a Voronoi diagram with GeoGebra on a pattern of nature or architecture. The participants can try this with provided patterns and prepared applets (https://www.geogebra.org/m/ard9kenz#chapter/373251), or they take their own pictures and investigate them with GeoGebra (Figure 5).

Figure 5: Modelling Voronoi diagrams with GeoGebra

Lindenbauer and Reichenberger

Task 4: What would you like to design? - 3D printable Voronoi patterns

Shaping architectural elements and structural forms using the Voronoi diagram is a trend in architectural design [5]. First, students should search and investigate various objects that were designed by artists using Voronoi diagrams (e.g., https://www.geogebra.org/m/zehpyhyv). Finally, the participants can design their own individual object utilizing Voronoi patterns with Tinkercad (https://www.tinkercad.com) (Figure 6). We decided to use this software because it provides easy access to 3D printing of Voronoi diagrams. For this final step students should already have some experience in working with Tinkercad.

Figure 6: 3D printed Voronoi eggcup (https://www.geogebra.org/m/zehpyhyv)

Final Remarks

This lesson plan was already conducted with grade 11 students from an Austrian high school. Several of these students will support us during the workshop in order to share their experiences with the participants. GeoGebra Book “Voronoi Diagram - Workshop” (https://www.geogebra.org/m/ard9kenz) provides a collection of all workshop materials.

References

[1] C. Baudson and E. Klein. Berechnung und Visualisierung von Voronoi-Diagrammen in 3D. Diplomarbeit, Rheinische Friedrich-Wilhelms-Universität Bonn, 2006. [2] S. Bento, H. Ferreira, and A. Hall. “Voronoi Diagrams: Didactical and Artistic Applications.” Bridges Conference Proceedings, Stockholm, Sweden, July 25–29, 2018, pp. 355–358. https://archive.bridgesmathart.org/2018/bridges2018-355.pdf [3] T. Biedl, M. Held, and S. Huber. “Recognizing Straight Skeletons and Voronoi Diagrams and Reconstructing their Input.” 10th International Symposium on Voronoi Diagrams in Science and Engineering, St. Petersburg, Russia, July 8-10, 2013, pp. 37-46. [4] J. B. Calonge and L. M. Yagüe. “Fostering Creativity in the Teaching of Mathematics with Project Based Learning.” Bridges Conference Proceedings, Jyväskylä, Finland, August 9–13, 2016, pp. 57–64. https://archive.bridgesmathart.org/2016/bridges2016-57.pdf [5] E. Gawell and A. Nowak. “Voronoi tessellation in shaping the architectural form from flat rod structure.” PhD Interdisciplinary Journal, 2015, pp. 47–55. [6] G. Glaeser. Wie aus der Zahl ein Zebra wird - Ein mathematisches Fotoshooting. Spektrum Akademischer Verlag, Heidelberg, 2011. [7] A. Gooddijn, M. Kindt, and W. Reuter. Geometry with Applications and Proofs Advanced Geometry for Senior High School, Student Text and Background Information. Sense Publishers, Rotterdam, 2014. [8] D. Hartvigsen. “Recognizing Voronoi Diagrams with Linear Programming.” ORSA Journal on Computing, . 4, no. 4, 1992, pp. 369–374. [9] C. Rousseau and Y. Saint-Aubin. Mathematik und Technologie. Springer Spektrum, Berlin, Heidelberg, 2012.