Circle Packings – Week 4

Have you ever hiked with a group of mathematicians? Me neither — until yesterday. This week, Professor Bowers hosted a circle packing workshop here at JMU where various researchers in the field came together to explore, discuss, and collaborate on all things circle-packing. I was extremely lucky that it took place during my time here with the REU program, as I can truthfully say it has been my most educative, and at the same time, most exciting, week. At every lunch, dinner, coffee outing, there was conversation about different circle packing problems, drawings and outlines of proofs on napkins…even the little napkin wrappers. The 30 minute ride to our hike was filled with math riddles and more intellectual discussion. When we reached the peak of the mountain, amidst soaking up the stellar view, we pondered some more problems and joked that we probably scared a couple of people off the mountain with all of our math talk. I’ve never been with so many extremely intelligent, enthusiastic, and down-to-earth people all at once.  It really has been such an awe-inspiring experience. Which makes me pretty teary-eyed that the week is over.

Amidst all of the additional circle packing discussion, we did in fact get the Voronoi diagrams working! We added code to the library that takes in a convex hull and then computes the Voronoi diagram of the hull. Then we created a couple of python scripts to draw the Voronoi diagrams of various packings: some simple cases with 3 disks, and then some more advanced cases with 12 – 14 disks. Here is an example of a 14-disk packing showing the packing, convex hull, and finally the corresponding Voronoi diagram.
Screen Shot 2017-06-09 at 9.30.40 AM.png             Screen Shot 2017-06-09 at 9.31.20 AM.png                  Screen Shot 2017-06-09 at 9.31.37 AM.png
  Fig. 1: Circle packing                        Fig. 2: Circle packing and convex hull           Fig. 3: Circle packing, convex hull, Voronoi Diagram
                  Screen Shot 2017-06-09 at 9.31.47 AM.png                   Screen Shot 2017-06-09 at 9.32.02 AM.png
                   Fig. 4: Circle packing and Voronoi Diagram                                     Fig. 5: Voronoi Diagram
In order to store a convex hull, we use a data structure known as a doubly connected edge list, or DCEL for short. The DCEL structure is ideal for computing things such as convex hulls as it stores subdivisions of polygons, by storing vertices, faces, edges, and what are known as half-edges, of a subdivision. Right now, our Voronoi Diagram algorithm takes in a convex hull, stored in a DCEL, and simply returns a list of circle arcs that represent the edges of the Voronoi diagram, with the source and target points of the circle arcs equivalent to the vertices of the diagram. However, this does not contain all of the information we may want. Ideally what we would like to do, is, given a convex hull, have the algorithm compute the Voronoi Diagram and return it as another DCEL, so that it contains relational information between its various edges and vertices as well.  Hopefully we will be able to update our algorithm to include this in the upcoming week.
Additionally, this week I also created a python script that generates random points on the sphere and then computes the convex hull of these random points. Afterwards, we figured it would be beneficial to add code directly to the library to do this, and so I added a function within our convex hull code that, given a specific number of points, would randomly generate that many points and then compute the convex hull.

Screen Shot 2017-06-09 at 9.46.15 AM.png

Fig. 6: Randomly generated points on the sphere and their convex hull   


Now that we have Voronoi diagrams up and running, we are that much closer to the soap bubble part of the project. I’m excited to get started with this part, as we’ll be using our circle packing library and potentially will be working with machine learning techniques to scan and display soap bubble configurations, which should look exactly like our Voronoi diagrams!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s