W. Lauritz Petersen and Dr. Denise Halverson, Mathematics

Our project consisted of several components with the end goal being: given n points on the ktorus (a donut with k number of holes), what would the shortest path network be to connect all the n points (network meaning a network of paths connecting each of the n-points). For example, Figure 1 shows a path network between four points. This general case turned out to be a much more involved question than we had initially anticipated and while we did not reach an end conclusion, we made huge strides in our understanding of the problem and a plan to tackle the larger question. In deconstructing the problem we needed the proper theoretical models to understand the configuration of points connected with the shortest path on the k-torus. Also, we needed to narrow the question and begin with a specific number of points. Instead of dealing with n points on the k-torus in general, we began our research by considering three, four, five, six, seven and eight points equally spaced around the edge of a circle. These specialized cases will eventually allow us to generalize to a greater number of points that will be spaced around the edge of a circle or an even broader case when the points are at randomly placed. In order to understand the networks between these n points on the k-torus, we researched the theoretical models that represented the surface of the k-torus these models being the different representations of the hyperbolic plane. After we researched and understood these models, we ran some preliminary experiments with a freeware package called “Surface Evolver.” Evolver inputs a data file we created that contained the general network structure and outputs the minimum line segments of the network, meaning that through a repeated process, Evolver shortens each segment of the network until reaching a state of equilibrium. This was the stage that we reached. The following is an outline of the research completed.

The surface of the single torus (Figure 2) can be modeled by the Euclidean plane while the ktorus has some interesting properties that makes its surface very different from the Euclidean plane. We can mathematically represent these non-Euclidean properties by modeling our paths and points in the hyperbolic plane and performing our analysis there in hyperbolic space. To illustrate this difference between the Euclidean plane and the hyperbolic plane, consider the ratio of the radius of a circle with its circumference; in the Euclidean plane as the radius of the circle gets larger the circumference increases with a proportionality constant of 2p but in the hyperbolic plane the circumference increases exponentially (not proportionally) as the radius increases.

Before we could do any of our analysis, we researched a few of the theoretical models that could represent the hyperbolic plane in the Euclidean plane. After careful consideration we chose three models that best worked for us. The first model we worked with was the Klein disk model. Because of considerations with Evolver, we chose this to be the model that we used within Evolver itself. This was done because of the way straight lines were represented in the Klein disk model. In this model straight lines appear as straight lines (see Figure 3). Another model used to visualize networks in the hyperbolic plane was the Poincaré disk model. In this model the shortest path between two points appears as a circular arc connecting the two points and is perpendicular to the disk at each of its endpoints. Figure 4 shows the shortest path between two points in this model. We found that using this model was the easiest way for us to visualize the use of hyperbolic trigonometry. The third model used was the Upper Half Plane model. In this model again the shortest path between two points is represented as a circular arc centered on the x-axis of the upper half plane (Figure 5). This model proved to be the easiest in which to do actual calculations of distance because of its direct connection to complex analysis and the complex plane.

Another portion of our research was the creation of different geometric combinatorial networks that the network of points would take on. In Figure 6 we can see the four ways that six points equally spaced on the edge of a circle could be connected by a network. For each of the three, four, five, six, seven and eight point cases, we needed to create all the possible geometric combinatorial networks in order to run them each through Surface Evolver and see which network experimentally was the shortest. This portion of the project took the majority of time but we did develop an algorithm that could be programmed into a software package that would create all the possibilities for network configurations and save them in a format that could then be run through Evolver. While working on this algorithm, we discovered and proved that the shortest network between n points will have n-2 inner nodes and 2n-3 line segments unless the shortest path was directly around the outer ring of points as illustrated in the third image in Figure 6. An illustration of inner nodes and line segments for six points is shown in Figure 6. One problem with the algorithm to create the different combinatorial networks was that it would create the same configuration repeated times. To solve this, we have partially created a second algorithm that would eliminate networks that were the same. Each of these algorithms could be programmed into one software package to create data files for Evolver in order to experimentally narrow the choices for the network minimizers.

The last portion of our completed research was the analysis of the six, seven and eight point cases using Evolver. We found that when we ran the experiments on the topologies for six, seven and eight points, there was a dependence on the radius of the circle that each of the six, seven or eight points was on. For example, for small radii (less that 0.3) we found that the minimizer was the Euclidean minimizer but when we increased the radius (between 0.3 and 0.99999 and other intermediate values all less than 1.0), the minimizer would change between the different combinatorial networks. This was most apparent with the eight different networks on eight points. Experimentally, we were able to determine the minimizing network for six, seven and eight points when the radius of the circle was very large (ie. close to 1.0). Overall we accomplished much of the research we had proposed and have laid a solid foundation for continuing research to be done in the future to solve the question in general.