Technical Terms:
central place theory, Diophantine, fractal, hierarchy, pixel, self-similar, Steiner transformation, Steiner tree.
Link to Chapter 8 Complement.
The Internet is the newest player in the moving market scenario: in the case of the Internet, however, the market comes right onto our desktop instead of merely to the town square! It offers exciting possibilities for getting initial producer in direct contact with end-user: the middle-level entrepreneur may be challenged to create a broad class of services that goes well beyond those typically provided to our traditional society. The broad concept of the "moving market" is one that is as old as nomadism: shepherds move their flocks around in response to changing grazing and weather patterns. "Periodic" marketing has long been common in a variety of the Earth's nations. Markets move in response to low-level demand patterns and in so doing may also create added demand. There is a delicate balance in the symmetry between market and end-user in both traditional and contemporary approaches to the moving market. If the Internet balance is tipped too far in one direction there is risk of leaving out huge segments of the global population in this electronic transformation, creating an even greater gulf between the "haves" and the "have-nots". If it is tipped too far in the other direction, development of the process itself and associated global economic transformations of the marketplace may become hazardously stalled. If synthesis of competing viewpoints finds a balance between extremes, then the Internet offers (at the very least) an opportunity to close gaps and to promote a vibrant, thriving global communications and trading environment. These complex issues will no doubt remain complex. What we offer here is a glimpse at a few, of many, ways to look at change in spatial structure under transformation.
The capabilities of the Internet, together with numerous assists from the marvelous technological devices that keep popping up in this contemporary revolution, helped us to weave together a document from a physical standpoint; from a conceptual standpoint, however, it is the concept of transformation that is the backcloth against which all the weaving takes place. From D'Arcy Thompson's fish (reprinted with the permission of Cambridge University Press) and map projections (Tobler, 1961), to the one-point compactification of the sphere and mapping on developable surfaces, to map coloring, to chirality and the structure of a pneumatic network, to mapping of the antipodes and various other non-Euclidean challenges. In this chapter, we consider two particular transformations that offer ways of looking at symmetry of various kinds: the Steiner transformation and the fractal transformation.
Steiner's problem is to find a shortest route joining an arbitrary, but finite, number of points in the plane. These geometric points may be viewed as graph-theoretic nodes and the geometric lines joining them viewed as graph-theoretic edges. The nodes may represent any of a variety of geographic objects whose location can be captured as a point at some geographic scale: a city may be a broad region at one scale yet at a more global scale may be considered a geometric point or a graph-theoretic node. The edges represent any sort of connection between nodes: from physical ties such as railroad tracks to cultural ties such as similar religious orientation to virtual ties across the Internet. The solution to finding a shortest route is a graph-theoretic tree of minimum length and this tree may include nodes not given in the original set. The Steiner algorithm, unlike algorithms in earlier chapters, may require the introduction of new nodes. Any new node, chosen to reduce total tree length joining the original set of nodes, may be chosen from an infinite set of possible positions.
Much of the earlier research on finding Steiner trees has appeared in the mathematics and in the applied mathematics and telephone engineering literature. Because a Steiner tree is one of shortest length, it minimizes total construction costs (in a broad sense). It is a desirable routing strategy when the cost of network construction outweighs other network costs. The task of finding a Steiner tree can be a monumental one: it is NP-complete that is, not solvable, from a computational standpoint, in polynomial time (Graham, Garey, and Johnson). When new points are added to reduce total network length, Hwang and Du have shown that the length of the network cannot be reduced by a factor of more than 1- 0.5(√3) or about 13%.
To find any path, let alone a shortest path, from A to B is a concern of enduring interest. Ariadne's thread offered Theseus an escape route from the labyrinth after he had slain the Minotaur. Hansel and Gretel hoped to retrace their steps out of the woods using a trail of bread crumbs, and Alice tried to discover a path to the top of a hill to better view the garden of live flowers. Mazes and labyrinths endure as popular forms of entertainment as well as fascinating formations in formal gardens. Analysis of mazes produces sets of rules for their solution. The puzzle of the maze is considered solved once the existence of a path through it, satisfying the given spatial constraints, has been found. If that solution is unique, then the maze generates no natural and immediate directions for further consideration.
If, however, the maze admits more than one path as a solution, then one asks: of all the paths through the maze, which is the shortest (longest)? (See Berge for a similar broad approach to problems of this sort.) If the physical landscape represents the spatial constraints of the maze, then this question might involve finding the shortest route for traveling from one location to another with distance measured in time, cost, or Euclidean distance. If each route requires the inclusion of a specified set of intervening locations as part of the given spatial structure, then the question becomes the so-called "travelling salesman" problem which is soluble in theory but which requires large numbers of calculations when only a relative small number of intervening locations are included.
Neither the maze nor the traveling salesman problem requires the route to branch. If the route connecting two or more places branches in order to pass through intervening locations, the problem is still to determine which of the branched trees is the shortest. This situation describes the minimal spanning tree problem. Kruskal and Prim published the earliest efficient algorithms for its solution. Their approaches rely on indexing the edge set according to length and on replacing, recursively in some sequencing pattern, edges of candidate trees.
Both traveling salesman and minimum spanning tree paths in a finite distribution of nodes generally assume uniformity of carrying capacity among all possible routes. If varying carrying capacities are assigned to alternate routes then economic considerations may be superimposed as well when the routing is represented along edges of a directed graph. The source may represent a location for supply and the sink a location of demand. A natural question is to ask what might be a maximal flow across the network from the source to the sink, to satisfy demand. This consideration transforms the undirected graph of the maze to the directed graph of the so-called "transportation problem."
Gaspard Monge, the French descriptive/projective geometer of the eighteenth century was apparently the first to tackle the transportation problem. More recent interest dates to the 1940s: Hitchcock determined optimal economic distribution of flow from a set of sources to a set of sinks, while Dantzig, used linear programming to consider similar situations. Dantzig's simplex method of linear programming (another NP complete algorithm) is effective for solving the transportation problem; it is not, however, necessarily efficient computationally, for it may involve rejecting a large number of choices as candidate routes. The simplex method is not well suited to Steiner's problem. The objective function of the simplex method generally fails to be well defined, unless pattern of connection within the solution tree is specified at the outset, when there are more than three points in the prescribed distribution of original locations. Such initial specification on tree type, however, means that often a shortest path is not found. In contrast to using linear programming to maximize an objective function over an entire set of feasible solutions determined at the outset, Bellman's dynamic programming permits decisions regarding optimum solution to be made at a set of stages during the actual solution process, often permitting reduction in numbers of calculations; unfortunately, it does not appear well-suited to Steiner's problem. Ford and Fulkerson's max-flow, min-cut theorem permits solution of the transportation problem by observing that flow along a given path of the network is constrained by the link in that path with minimum carrying capacity. In contrast to the linear programming approaches, Ford and Fulkerson use economic constraints on the spatial structure of the network to determine optimal gain from the network. Modifications and generalizations of the Ford and Fulkerson method range from extending it to a set of sources and a set of sinks, to modifying carrying capacities of links to accommodate variation along the route from source to sink.
Each of algorithms broadly discussed above, from paths through a maze to various solutions for the transportation problem, is such that a small shift in nodes intermediate between origin and destination may produce an improvement in optimal path length through the network. The Steiner problem, instead, introduces new intermediate nodes and selects as the new nodes that set that does produce the shortest tree through the network so that no shift in intermediate nodes can improve shortest path length. Procedure to execute the determination of the optimal set is complex. We show one way to find the Steiner network in a triangle (in a way that generalizes) and then illustrate it for a pentagon of original points. See the Bibliography for more entry points to the literature. Detail for locating candidates for the generalized Steiner network is available in a variety of references. Melzak published an algorithm in 1961 that proved existence of a solution to the generalized Steiner problem but exhibited none of the detail. Gilbert and Pollak later extend Melzak's procedure to deal with degenerate Steiner networks (paths that follow, to some extent, the convex hull of the set of n nodes), as does Cockayne.
Steiner's original problem consists of determining the tree of shortest length in the Euclidean plane, linking three nodes, v1, v2, and v3. If v1, v2, v3 form a triangle with one angle greater than or equal to 120 degrees, then the shortest path is along the two sides of the triangle that form that angle. Otherwise, the shortest path is found by locating a point, Sp (so-called Steiner point), such that |Spv1|+|Spv2|+|Spv3| is minimized. The edges Spv1, Spv2, and Spv3 form the Steiner network on (v1v2v3) and these edges form an angle of 120 degrees to each other at the Steiner point (Figure 8.1).
Figure 8.1. This figure displays a triangle, Steiner point (interior to the triangle), and Steiner network (green edges). The angles at the interior point are each estimated (but clearly are not) to be 120 degrees.
The style of construction shown below is based on the style of proof of J. E. Hoffmann, found in Coxeter. It served as the basis for generalization to larger numbers of points. First, choose any point, P, in the interior of the triangle v1v2v3. Join P to each vertex of the triangle. The goal is to minimize the sum |Pv1|+|Pv2|+|Pv3|. We do not know how to do that, so we transform that sum into one that we do know how to minimize. Rotate triangle v1Pv2 outward through 60 degrees about v1 as a center. Label the new points: P' and v2' (Figure 8.2). Triangle v1Pv2 is congruent to triangle v1P'v2' since rotation is a rigid motion. Thus, |P'v1| = |Pv1|. However, angle (Pv1P') is 60 degrees (by choice of rotation); hence, triangle P'v1P is equilateral and therefore |Pv1| = |PP'|. Therefore the sum |Pv1|+|Pv2|+|Pv3| has been transformed to the sum |PP'|+|P'v2|+|Pv3| and that length is minimized as a straight-line segment joining v2' and v3. (Here is where the assumption that the transformation is taking place in the Euclidean plane enters: the shortest distance between two points is along a straight line segment; it is an interesting research question to remove this condition and work in non-Euclidean geometries.) Thus, the Steiner point (the intermediate point that will necessarily produce a shortest total length network) lies somewhere along the line v2'v3. The problem of finding the intermediate point has been reduced from searching a plane region to searching along a line segment (Figure 8.2 animates the construction). It is not hard to see, looking at the construction and the fact that the initial rotation was through 60 degrees, that the angles at Sp must all be 120 degrees. Thus, Sp also lies along an arc of a circle determined by v1, v2, and v2' (again, because the initial rotation was through 60 degrees).
Figure 8.2. This figure displays Hoffmann's style of construction of a Steiner network. The search for the intermediate point is reduced from searching in a plane region to searching along a line segment in this construction. Compare the location of the constructed Steiner network here, in red, to the location of the estimated network, in green, in Figure 8.1.
The construction for finding a candidate Steiner network within a pentagon involves a similar construction: insert intermediate points P1, P2, and P3 in an arbitrary position and then use those to reduce the situation to the previous case (case of the triangle) and then solve (that is, the construction proceeds by induction). The animated image in Figure 8.3 suggests the procedure; the point Q is the arbitrary point inside the triangle (the same as P2, a labeling difference to emphasize the reduction of pentagon to triangle).
Figure 8.3. This figure shows an extension of the construction for a triangle, in Figure 8.2, to a pentagon. The point Q inside the triangle represents the same location as the arbitrary P2 inside the pentagon.
There are various ways in which the subtree on nodes P1, P2, and P3 may be joined to the pentagon. The subtree might take various topological forms, as well. These extra considerations add to the complexity of finding Steiner networks; however, the general procedure proceeds by induction (separated into odd and even cases) on the order of nodes.
When one is looking at a geographic problem from a regional perspective, it is often the case that there are a number of cells, representing a number of different municipalities. Each cell may have its own network within it; yet, one might wish to consider some sort of broader, overall regional tree linking the municipalities. When the local trees can be captured as Steiner trees, the following transformation can be used to eliminate redundancy in connection at a scale broader than the local yet obtain a tree that retains many of the characteristics of the individual local networks.
Given a network of contiguous, closed polygonal cells. Locate the Steiner network within each cell and discard the initially given structure: that process is what we refer to as a Steiner transformation (Arlinghaus, 1977). Examine the new network; if closed polygonal cells remain, repeat the procedure. Continue the procedure until no closed polygonal cells remain (if possible). Network edges not included in the boundary of a closed polygonal cell remain invariant under the transformation. The resulting tree, when it exists, is irreducible. A finite sequence of Steiner transformations is illustrated in Figure 8.4.
Figure 8.4. Steiner transformation carries the local networks (only roughly imitating Steiner position to illustrate the point) in a set of contiguous cells to a single regional tree.
In the example of Figure 8.4, the sequence of successive applications of the transformation terminates rapidly. Depending on the local network structure, the sequence may terminate only after numerous iterations of the transformation, or it may never terminate (see Arlinghaus, 1977 and 1989 for conditions for various states). A sequence of successive applications of the Steiner transformation can help to resolve scale problems by drawing together local and global form and therefore offer ways to look at symmetry across, rather than merely within, layers of a spatial hierarchy.
In nature, parts clearly do fit together into real structures, and the parts are affected by their environment. The problem is largely one of understanding. The mystery that remains lies largely in the nature of structural hierarchy, for the human mind can examine nature on many different scales sequentially, but not simultaneously. C. S. Smith in A. Loeb, 1976, p. xiv.
One hierarchy that is persistent in nature is the hexagonal hierarchy: bees use it and soap bubbles naturally compress to it. Each tiled layer of an hexagonal hierarchy is packed as closely as possible; there are no gaps and a tiling by hexagons is more tightly packed than a tiling by squares. Of particular interest here, however, is the pattern the layers of hexagons form with respect to each other moving vertically through the hierarchy. Are smaller hexagons from one layer nested within larger ones from another layer? Alternatively, are they twisted in relation to another layer so that smaller hexagons overfit and underfit larger ones? One classical interpretation of this concern has been expressed in a marketing, transportation, and administrative context, as so-called "central place theory" (Christaller, 1933; Lösch, 1949). In it, the smallest hexagon in the hierarchy is a basic unit as a fundamental trade area. Larger hexagons in other layers represent larger trade areas within which there are higher demands for goods and services. One might associate size of store, for example, with size of hexagon. Larger stores, such as department stores, have larger trade areas: people are more willing to travel to go to a department store than they are to go to a corner party store. One imagines, in this vein, a sequence of layers of hexagons successive sizes. There is an infinite number of possibilities to describe the manner in which these layers are oriented with respect to one another, as there also is for the size of the cell as one moves from layer to layer.
Concepts from fractal geometry can be used to capture pattern in hexagonal hierarchies (Arlinghaus, 1985; Arlinghaus and Arlinghaus, 1989). They provide replicable, rigorous support for earlier intuitive notions and permit solution of previously unsolved problems hiding below the integral surface of previous analyses (Dacey, 1965; Marshall, 1975). The fractal transformation for hexagonal hierarchies involves successive replacement of shape as suggested in the examples of Figure 8.5 and Figure 8.6. The fractal transformation, like the Steiner transformation, is based on successive replacement of form that allows one to overcome geographic scale problems. The similarity ends there. The Steiner transformation is based on connectivity patterns only; the fractal transformation introduces Euclidean distance, in addition. They are contrasting approaches, graph theoretic and geometric, to looking at certain patterns.
Figure 8.5. This figure shows a fractally generated hexagonal hierarchy in which each larger hierarchical unit contains the equivalent of four, self-similar, smaller hierarchical units.
Figure 8.6. This figure shows a fractally generated hexagonal hierarchy in which each larger hierarchical unit contains the equivalent of seven, self-similar, smaller hierarchical units.
In Figure 8.5, as the eye moves toward the right, the larger hierarchical unit contains four copies of the unit from the previous construction. Thus, the middle unit contains four hexagons. The unit to the far right contains four copies of the middle unit (and therefore, 42=16 copies of the hexagon). Similarly, in Figure 8.6, the middle unit contains seven hexagons and the unit to the far right contains seven copies of the middle unit (and therefore, 72 = 49 copies of the hexagon). The spacing between the center of the original hexagon (on the left) and new competitors determines whether four, seven, or some other number becomes a constant of the hierarchy. If locations for new competitors are viewed to be situated at integral lattice points, then we can associate with each lattice point the value suggested by the construction above. Assume the origin at (0,0). Then the following association is created by the Diophantine equation x2+xy+y2 (Table 8.1). The first column gives integral lattice point coordinate values; the second column shows how many self-similar smaller units will determine a constant of the hierarchy.
(1,1) |
3 |
(1,2) |
7 (Figure 8.6) |
(0,2) |
4 (Figure 8.5) |
(0,3) |
9 |
(0,4) |
16 |
(0,5) |
25 |
(0,6) |
36 |
(0,7) |
49 |
(0,8) |
64 |
(0,9) |
81 |
(0,10) |
100 |
Table 8.1. This table displays lattice points and associated constants of hexagonal hierarchies.
Thus, while there are infinitely many hierarchies of this sort, there is not one for every integral value. It is convenient to represent the values as attached to lattice points in an oblique coordinate system (Figure 8.7). Thus, in Figure 8.1, the lattice point with coordinate pair (1,3) has a value of 13 attached to it. Therefore, the associated fractal transformation will have 13 as a constant of the hierarchy: there will be 13 self-similar images as one moves through successive stages in the hierarchy.
Our rectilinearly trained minds tend to take oblique axis systems and square them off to be orthogonal. When that is done in this case, the corresponding Diophantine equation simply becomes Pythagorean: x2+y2 to determine the weights to associate with the lattice point (x,y) (Figure 8.7).
Figure 8.7. Lattice points set in oblique and orthogonal axes; Diophantine weights are a constant of associated hierarchies, hexagonal and square.
Figure 8.8 shows the square hierarchies that correspond to the hexagonal hierarchies of Figures 8.5 and 8.6. The top set is associated with the lattice point (0,2) and the bottom set with the lattice point (1,2). In the case of (0,2) both the hexagonal and the square hierarchies have the same self-similarity constant of 4. In the case of (1,2) the hexagonal hierarchy has a constant of 7 and the square hierarchy a value of 5. The hexagonal self-similarity constants are identical to constants identified in the classical central place literature (Christaller, 1933 and Lösch, 1949).
Figure 8.8. Sequences showing fractal generation of hexagonal and square hierarchies associated with lattice points (0,2), top, and (1,2) bottom.
The constructions above, if carried out infinitely, might or might not "fill" a portion of the plane with the ever-bending boundary segments. If they did fill a plane region, then the sequence would have value "2"; if not, then it would have some value somewhere between 1, the Euclidean dimension of a line segment or of a sequence of line segments, and 2, the Euclidean dimension of a region. Fractional dimension (fractal), between integers, is a concept new to many, although most of us recognize partially filled space in our day-to-day encounters with the real world. One method to calculate this partial filling is with the following formula for fractional dimension (Mandelbrot, 1983): F = (log n)/(0.5 log K), where K and n are related to the problem at hand in some natural fashion. We use n as the number of edges in the sequence generator, the shape over the arrowhead in Figures 8.5, 8.6, 8.8, and K as the number of self-similar shapes so generated as a constant of the hierarchy. Hence, in Figure 8.8, the first sequence, if carried out indefinitely would yield a fractional dimension of: F=(log 3)/(0.5 log 4)=1.585. Table 8.2 shows values for fractional dimensions calculated for several sample hierarchies based on squares and hexagons. Note that in all cases, the square hierarchies fill more space than do the hexagonal hierarchies. That fact may have interesting implications in a variety of applications.
Coordinates |
Squares: dimension |
Hexagons: dimension |
(1,1) |
2.0 |
1.262 |
(1,2) (Figure 8.5) |
1.365 |
1.129 |
(0,2) (Figure 8.6) |
2.0 |
1.585 |
(0,3) |
1.465 |
1.262 |
(0,4) |
1.5 |
1.161 |
(0,5) |
1.365 |
1.209 |
(0,6) |
1.387 |
1.161 |
(0,7) |
1.318 |
1.129 |
(0,8) |
1.333 |
1.153 |
(0,9) |
1.290 |
1.131 |
(0,10) |
1.301 |
1.114 |
Table 8.2. Fractal dimensions associated with selected lattice points.
The concept of mobile telecommunications is straightforward (Chia 1992). A set of microcell base stations, each of which can transmit and receive electronic information, is spread across a geographic space as a network of stations, each with its own tributary area, a microcell, with which it communicates. Typically, one might think of the microcell base station as the center of a circular tributary area, with circular areas packed to cover a larger circular area. At the center of the larger circular area, a macrocell base station serves as an umbrella to relay information to the microcell base stations under it. Within this sort of mixed cell architecture, a vehicle carrying an onboard terminal (cell telephone) passes through the microcells and receives information on a continuing basis from the base station associated with the microcell the vehicle is currently traversing. This sort of hand-off of information is reminiscent of the hand-off of pneumatic carriers from one energy region to another that we saw within the Rohrpost. The idea of handover nodes, from relay race, to Rohrpost, to cell telephones, endures: the technology changes.
The size of the macrocell may be linked to the height of the tower. Some municipalities encourage competing service providers to "co-locate" their antennae on a single tower (City of Ann Arbor, discussions of City Planning Commission Ordinance Review Committee, 1997-2000). If the antennae are located too close to each other on a single tower, however, signal interference and less than optimal service are the result. To encourage co-location, thereby reducing the number of towers, taller towers must be built. Taller towers have larger macrocells when considered in the fine environment of a uniform plane. In the real world, topography, buildings, migrating birds and various existing elements in three-dimensional space may alter a planar base pattern. Many studies involving microcell networks are done, initially, in an abstract environment as a benchmark against which to evaluate others in less than optimal environments (Chia, 1992).
Within the abstract environment, imagine a set of macrocells all of the same size (set by tower height in response to municipal ordinances). As their tributary circular service areas abut each other, a layer of hexagons or a layer of squares emerges to fill space (depending on how one sets them down in some space-filling fashion leaving no interstitial regions). As microcell towers fill in between macrocell towers, a smaller layer of hexagons or squares emerges. Different patterns of nesting and orientation from one layer to the next depend on the arrangement and size of tower. As one lets the pattern go to infinity, one can measure its fractal dimension: the extent to which boundaries separating cells fill space. A mixed cell architecture of low fractal dimension would be one that reduces handover requirements and would therefore be, presumably, more likely to meet optimal service requirements than would one of higher fractal dimension and greater handover requirements. Table 8.2 shows a comparison of mixed cell architectures using the square as a base figure and the hexagon as a base figure. The central macrocell tower is located at (0,0). The table shows the lattice coordinates for a microcell base station, reflecting distance between macro and microcell towers, and the associated fractal dimension that comes from carrying out a fractal construction similar to those above in Figures 8.5 and 8.6 (Arlinghaus, 1993).
The hexagonal nets have boundaries that consistently fill less space than do the square nets. Unfortunately, current location strategy, that sees cell towers placed largely along freeways and secondarily along major surface routes, is more likely to mirror the square configuration, particularly in municipalities that employ a grid street network. Municipal planners face tough choices involving interesting tradeoffs.
Square pixels in a sequence on a cathode ray tube are separated by boundaries. When smaller squares are introduced, more lines separating pixels are therefore introduced. If one assumes that the interior of the pixel, and not its boundary, carries the content of the image, how much can one reduce the pixel size (to increase detail) and yet not lose content? There is trade-off between fineness of resolution and loss of content. The fractal sequences above suggest that the point of diminishing returns sets in at different places depending on the choice of basic pixel shape and on the manner in which pixel size might be altered. As one might allow resolution to increase indefinitely, Table 8.2 shows that only in the case of the square pixel does all content become obliterated (when the fractal dimension goes to 2). That same table also shows that in all cases the hexagonal pixel is a superior choice for basic pixel shape under the constraints outlined above for increased resolution (Arlinghaus, 1993).
From the symmetry of classical central place theory based on simple marketing concerns, to the more contemporary electronic environment of cell telephones and cathode ray tubes, the spatial transformation of moving across hexagonal or square hierarchies is one that endures. Indeed, the Internet itself is a spatial hierarchy: search engines and web guides serve major virtual tributary areas which in turn provide access to smaller virtual tributary areas and these in turn provide access to smaller tributary areas yet, until access reaches the single file level. Mathematical infrastructure remains, although superficial interpretation varies widely.