Voronoi Diagrams: Didactical and Artistic Applications

Year: 2018 Authors: Sandra Bento; Helena Ferreira; Andreia Hall

Core claim

Voronoi diagrams are simple, teachable geometric structures that can also generate rich artistic patterns, especially in quilts and classroom activities.

Topics

Voronoi diagrams, didactical tasks, art quilts, computational geometry

Domains

Euclidean geometry, computational geometry, Delaunay triangulation, perpendicular bisectors, textile art, quilt design, ornamental pattern, generative art

Methods

classroom activities, compass and straightedge construction, Wolfram demonstrations applet, visual pattern design

Media

paper, compass, straightedge, quilt fabric, Wolfram applet

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 2018 Conference Proceedings

Voronoi Diagrams: Didactical and Artistic Applications

Sandra Bento${}^1$, Helena Ferreira${}^2$ and Andreia Hall${}^3$

${}^1$University of Beira Interior, Portugal; sbento@ubi.pt

${}^2$CMA - Center of Mathematics and Applications, University of Beira Interior; helenaf@ubi.pt

${}^3$CIDMA, Center for Research in Mathematics and Applications, Department of Mathematics, University of Aveiro, Portugal; andreia.hall@ua.pt

Abstract

Research on Voronoi Diagrams evolved a great deal from the original setting where a network of polygons marks the separation of points by regions of influence. Multiple approaches have been taken to solve the elementary geometry problems of bisecting segments and intersecting half-planes. The methods vary according to the type of point, the distance used and the type of bisector. In this work we propose some didactical tasks based on creating Voronoi diagrams. We also present some artistic quilt work, designed with the help of a Wolfram demonstrations project applet, based on a convenient choice of the generating points of a Voronoi Diagram.

Introduction

In some animals’ skin or fur, as in some plants or landscapes, we can see a kind of polygonal distribution pattern that makes us wonder about some optimization strategies nature might have [2]. Modeling nature through adjacent polygonal areas is a method that goes back to Descartes. In his space decomposition diagram he surrounds all space matter that gravitates around each star by a polygonal line [1]. In the 19th century both Dirichlet and Voronoi (1868-1906) developed the initial steps in the mathematical theory behind the so called Voronoi Diagrams. Nowadays it is an important branch of Computational Geometry, with applications to many different research subjects, such as ecology, geophysics, architecture and medicine, strongly supported by computational science.

Working in the two-dimensional Euclidean plane ${\mathbb{R}}^2$, we can choose for the sites in a Voronoi diagram the set of points $\mathcal{P}=\{P_1,\dots ,P_n\}$ and the Euclidean distance $d$ between them. For each $i=1,\dots ,n$ the region

consisting of points that are closer to $P_i$ than to any other point in $S$, is called the Voronoi region of $P_i$. The set $\mathcal{V}(\mathcal{P})=\{V(P_1),\dots ,V(P_n)\}$ is called the Voronoi diagram (VD) of $\mathcal{P}$. All $V(P_i)$ are polygonal convex regions, so they are also called Voronoi polygons.

From this definition we easily check that if $\mathcal{P}$ has only 2 points then $\mathcal{V}(\mathcal{P})$ is formed by two half-planes defined by the perpendicular bisector of the line segment between them. If it has 3 non collinear points then each $V(P_i)$ is the intersection of the two half-planes containing $P_i$, defined by the two perpendicular bisectors between $P_i$ and each of the other two. For any other number of points $n⩾2$, $V(P_i)$ is a polygonal convex region defined by the intersection of $n-1$ half-planes containing $P_i$ and it has at most $n-1$ edges. If $\mathcal{V}(\mathcal{P})$ has no 3 collinear points and no 4 circumcentric points, then each vertex of the VD is the intersection point of exactly 3 edges and it is the circumcenter of a triangle with vertices in this edge adjacent points of $\mathcal{P}$. In this case there is a one-to-one correspondence between the family of vertices in $\mathcal{V}(\mathcal{P})$ and the family of circles containing exactly 3 points of $\mathcal{P}$. This gives a dual planar graph to a VD in the plane - the Delaunay Triangulation, where the interior of each triangle face is empty (empty circle property). As with other results and properties about edges and vertices of Voronoi diagrams, it is easy to understand

Bento, Ferreira and Hall

and illustrate but maybe not so easy to prove. Rigorous mathematical proofs are outside the scope of this presentation (see [?]). However, the visual illustration of some of the results briefly mentioned above can be used in the design of classroom tasks for children, or in the creation of some artwork. We present here some examples of didactic tasks and some artistic work based on Voronoi diagrams.

Didactical Applications

In this section we describe three didactical tasks based on Voronoi diagrams. The first task illustrates the intuitive construction of a Voronoi diagram generated by three non-collinear points. The second one illustrates the construction of a Voronoi diagram using a compass and a straightedge. Finally, the third one illustrates an application of the empty circle property. Figure 1 shows one of the resulting outputs for each task.

Busy Squirrels

Leandro the squirrel has several neighboring squirrels in Squirreland forest where he lives. On windy autumn days, as the sun rises, Squirreland forest wakes up with its soil covered with nuts. Each squirrel family quickly collects as many nuts as possible and in a flash of time all the nuts disappear! Experience taught these squirrels that they should pick up those nuts which are closer to their burrow than to any other. Three squirrel burrows are represented on a sheet of paper. Each squirrel burrow and family has its own color. Can you paint each nut with its conqueror color? Note the two-colored nuts along or close to the border lines in Figure 1(a).

The Forwarned Squirrel

Life experience tells Leandro he should not be farther from his burrow than from his neighbors’. Yet, stronger than his life experience is his wandering mind, always distracted by the crackle of autumn leaves. Well, life is to be enjoyed and he doesn’t want to waist time with distance calculations. So he decides to get the help of squirrel Euclides, the famous forest Geometer. Euclides has a Squirreland map where each squirrel burrow can be seen as a black dot. He also has a straightedge and a compass. Can you help Euclides draw a border line so that Leandro gets the maximum space but is never farther from his burrow than from his neighbors’?

(a) Busy squirrel, 3rd grade

(b) Farwarned squirrel, 6th grade

(c) Villain squirrel, 6th grade Figure 1: Squirrels activities completed by school children.

The Villain Squirrel

The fence built by Leandro with Euclides’ help was a success in Squirreland and became a trend, every squirrel built fences in a way that inside each fence he was closer to his burrow than to any other one. It is

Voronoi Diagrams: Didactical and Artistic Applications

then that they hear about a villain squirrel who intends to survive the winter with as many nuts stolen from neighbors as he can. Not only was he a thief squirrel but also a lazy one, so he wanted to make his burrow as close as possible to the largest number of neighbors. Knowing the villain’s mind, the other squirrels had the idea to build a trap in the place he would choose for his burrow. It was time to ask Euclides’ help once again. Can you help him find the best place for the daunting trap?

Artistic Applications

Voronoi diagrams can be used in the process of creating artworks. For instance, the Portuguese artist Leonel Moura has used Voronoi diagrams in several creations, including a whole series of paintings, Voronoi 2002, where the basic elements of Mondrian. Red, blue and yellow colors on a white background and a black grid are recreated within a Voronoi structure [5].

Most Voronoi diagrams form abstract patterns but a convenient choice of the generating centers may produce figurative results. Andreia Hall and Prudência Leite have created two pairs of quilts using Voronoi diagrams suggesting nature-related elements: Floral Voronoi I and II (see Figure 2 below) have been exhibited in Bridges 2010 [3] and Solar Voronoi I and II are on display at Bridges Stockholm (see Figure 3 below). The Voronoi diagrams underlying these quilts were generated using a Wolfram demonstrations project applet [7] and are shown in Figure 4.

Figure 2: “Floral Voronoi I” and “Floral Voronoi II” quilts, $55cm\times 55cm$ each.

Figure 3: “Solar Voronoi I” and “Solar Voronoi II” quilts, $58cm\times 60cm$ each.

Bento, Ferreira and Hall

(a)

(b)

(c) Figure 4: Voronoi diagrams used to create the quilts (a) Floral Voronoi I, (b) Floral Voronoi II, (c) Solar Voronoi I, (d) Solar Voronoi II.

(d)

Summary and Conclusions

Voronoi diagrams are a prolific source of inspiration both for artists and for teachers at school. Its mathematical content can be used in geometry classes not only to help learning the concept of a perpendicular bisector, but also to promote creativity through its application. The subject can be didactically explored even in more advanced math curricula. As suggested and exemplified by Craig Kaplan [4], the line contour of Voronoi regions of other objects in the plane, other than points, can be plane curves instead of polygonal lines. Conics can appear in this way. For example, the process of constructing an ellipse through paper folding by overlapping points of a circle with a fixed interior point can be seen as the mathematical process behind a Voronoi diagram similar to the presented Solar Voronoi artwork. You can observe an almost circumcentric distribution of points outside the Voronoi “sun”. The circle center together with the “sun” defining point can be the two foci of an ellipse. Voronoi diagrams have the advantage of being simple to understand and to apply, and yet powerful enough to generate a great diversity of patterns.

Acknowledgements

This work was supported in part by the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), through CIDMA - Center for Research and Development in Mathematics and Applications, within project UID/MAT/04106/2013, and CMA - Center of Mathematics and Applications, within project UID/MAT/00212/2013.

References

[1] F. Aurenhammer and R. Klein. “Voronoi Diagrams.” Handbook of Computational Geometry, ch 5 (Ed. J.-R. Sack and J. Urrutia). Amsterdam, Netherlands: North-Holland, 2000, pp. 201-290. [2] R. W. Fathauer. “Real-World Tessellations.” Bridges Conference Proceedings, Baltimore, USA, July 29 - August 02, 2015, pp. 107-112. http://archive.bridgesmathart.org/2015/bridges2015-107.. [3] A. Hall. “Floral Voronoi.” Bridges Art Exhibition Catalog, Pécs, Hungary, July 24-28, 2010, pp. 8. [4] C. S. Kaplan. “Voronoi Diagrams and Ornamental Design.” ISAMA ‘99, The First Annual Symposium of the International Society for the Arts, Mathematics, and Architecture, San Sebastian, Spain, June 7-11, 1999, pp. 277-283. [5] L. Moura. Internet Blog. 2008. https://arte2.wordpress.com/tag/galeria/. [6] J. O’Rourke. Computational Geometry in $C$ , second edition. Cambridge University Press, 1998. [7] E. Pegg Jr and J. Bryant. “Voronoi Diagrams.” Wolfram Demonstrations Project, Updated by T.W. Gray. http://demonstrations.wolfram.com/VoronoiDiagrams/.