Original Math Notes
All Seasons
Episode 401: Trust Metric--Interactive Computations--Explore the Math
Episode 401: Trust Metric
Using set covering deployment to optimally place police units
Scene 15:
INT. EPPES HOUSE - DINING ROOM/LIVING ROOM - MORNING

Set covering deployment

In "Trust Metric," Charlie attempts to aid police by finding an optimal positioning of law enforcement units patrolling downtown Los Angeles as a part of their ongoing fugitive manhunt. In Scene 15, Charlie proposes using set covering deployment to help achieve this goal:

                    ALAN
          Charlie, didn't you do something like
          this before -- chase curves --

                    CHARLIE
          Pursuit curves... and they're not
          really applicable --
               (off Alan)
          But you know, I've always suspected
          that the Set Covering Deployment
          Problem could be an invaluable aid in
          positioning police units...

Set covering deployment seeks an optimal stationing of troops in a set of regions so that a relatively small number of troop units can control a large geographic region. Charles S. ReVelle and Kenneth E. Rosing first described this in 2000, in a study of Emperor Constantine the Great's mobile field army placements to secure the Roman Empire. Set covering deployment can be mathematically formulated as a (0,1)-integer programming problem. Integer programming is a special case of linear programming, which refers to optimizing an outcome based on some set of constraints using a linear mathematical model, and (0,1)-integer programming means that all variables are required to be integers equal to either 0 or 1--in other words, the variables are binary.

Map of the Roman Empire

To formulate the Roman domination problem, consider the 8 provinces of the Constantinian Roman Empire illustrated above. Each region is represented as a white disk, and the red lines indicate region connections. Call a region secured if one or more field armies are stationed in that region, and call a region securable if a field army can be deployed to that area from an adjacent area. In addition, assume that a field army can only be deployed to an adjacent region if at least one army remains in the original region to provide logistical support. Also assume that each region contains at most two armies, as the number of available armies are limited and cannot be concentrated in any one region.

This problem can then be mathematically formulated by representing the Empire as a graph. Note that here, the word "graph" is a mathematician's usage of the term: not a plot of a function, but rather a collection of points (the vertex set V) and lines (the edge set E) connecting some subset of the points. We can then associate two binary variables X_i and Y_i with each vertex v_i (i.e., each province) in the vertex set V={v_1,...,v_n} of the Roman Empire graph which specify whether a first and second field army (respectively) is located at a given vertex v_i.

In the terminology of graph theory, the Roman Empire graph is a simple connected graph on eight vertices and with 13 edges. Here are several types of undirected graphs, including some particularly attractive named graphs encountered in mathematical graph theory. (To learn more about these graphs, click on their images.)

types of undirectled graphs pseudograph multigraph simple graph

various named graphs Clebsch graph complete graph on 16 nodes dodecahedral graph tesseract graph

In set covering deployment, the problem to be solved is to maximize the quantity \sum_{i=1}^n (X_i+Y_i) subject to the constraints

X_i > Y_i for all i

which guarantees that the first legion is stationed at a given vertex before a second can be,

X_i + \sum_{(v_i,v_j)} Y_j > 1 for all i

which guarantees that if v_i does not contain a field army, it has a neighbor with two field armies, and

X_i, Y_i \in {0, 1} for all i

which enforces the integer constraint (i.e., when combined with the first constraint, only zero, one, or two field armies may be placed in any given region). This integer programming problem can then be translated into matrix terms and solved using standard techniques to find the minimum number of field armies needed to secure the Constantinian Roman Empire.

The lighthouse analogy

In reality, Charlie's optimization problem is somewhat different: to maximize the area that can be reconnoitered by a fixed-size police force in downtown Los Angeles. It's different because police may assume any positions instead of being restricted to a set of discrete locations, and because it involves no secondary considerations such as "empty" regions requiring two neighboring police units to be present. Charlie describes it using the analogy of lighthouses:

                    CHARLIE (cont'd)
          But lighthouses are a limited
          resource; they cost time, money,
          materials. Using Set Covering
          Deployment --

-- boom up into an AERIAL OF THE COASTLINE (not a straight
line, but jagged) -- the sweeping lights becoming CIRCLES OF
LIGHT, intersecting --

          -- we determine the best placement of
          our limited number of lighthouses to
          illuminate the ocean.

-- the circles connecting by lines, becoming a geometrical
organization that blankets the coast.

Covering problems

Charlie's lighthouse model describes what is mathematically known as a covering problem: given a set of geometric shapes, find an arrangement that maximizes the fraction of a specified area that they can cover. In the case of lighthouses, the region of the coast covered is the fraction from which at least one lighthouse can be seen. In the case of police officers in downtown Los Angeles, to first approximation (ignoring local topography such as streets, building, etc.) we can assume that each officer "covers" a circular region (i.e., a disk) whose size is proportional to the distance that officer can see (or run). Taking the search region as a square set of city blocks (shown in gray below), the following visualization shows a configuration of randomly distributed police officers with random coverage radii, giving an arrangement that covers only 50% of the search region.

randomly distributed police

Obviously, the larger the size of the police force and the larger the coverage radii of individual police units, the higher the fraction of area that can be covered. However, optimal placement gives the best coverage possible for a fixed set of police units. In the case above, it turns out to be possible to arrange the six disks so that they have no overlap, so the maximum coverage is given by pi(r_1^2 + ... + r_6^2) approx 0.69, i.e., the sum of the disk areas, each of which is given by pi times the radius squared, where radii are measured in units of the edge length of the square.

In general, achieving optimal coverage requires minimizing disk overlap, as well as minimizing the amount by which disks extend outside the area of surveillance. As you can see below, an optimal solution is not necessarily unique; in this case, there are several separate disk arrangements that all share an optimal 69% coverage. You can interactively explore optimal coverages for different numbers of police units using the applet at the top of this page.

optimally positioned police

Global optimization

Covering problems are a form of global optimization problem. In general, such problems are difficult to solve even approximately, let alone exactly. In the more complicated case of placing even as many as ten police, one can imagine moving them around "by hand." But in general, as the number of objects becomes large, problems of this type become unmanageable using not only "hand" methods, but also using any sort of combinatorial methods. Effective practical methods are thus needed.

As seen above in the case of Roman domineering, addressing a problem mathematically generally requires two steps: (1) formulating the problem mathematically and (2) using appropriate methods to find a solution. Depending on the nature of the problem, one of these steps may be harder than the other. In the idealized police deployment problem, step 1 is "easy," as the problem can be rather succinctly formulated as maximizing the function

I(x_1, ..., x_n) = int_{[0,1]^2} [[vee_{i=1}^n (|x-x_i| < r_i)]] dx dy

--that is, finding the set of points x_i=(x_i,y_i) constrained to the unit square (0 ≤ x_i, y_i ≤1) that give max_{x_i,y_i} I(x_1, ..., x_n), where [[S]]=cases{0 if S is false; 1 if S is true is the Iverson bracket, |v| denotes a vector norm, and ∨ is the logical OR operator. Here, we have made the assumptions that a given police officer's covering radius r_i is fixed regardless of the officer's position, and that we know or can estimate a value of this radius for each police officer. Finally, the symbol \int_{[0,1]^2} ... dx dy denotes a double integral over the unit square that gives the total amount of area covered by police. So the mathematical formulation above simply says, "For a given set of police positions and coverage radii, find all regions in the unit square covered by at least one police officer, sum their areas (making sure to count regions of overlap only once), and maximize this area for fixed radii over all possible police positions."

Once the problem has been mathematically formulated, it can be solved using one of a number of optimization algorithms, such as the following (all of which, incidentally, are built into the Mathematica command NMaximize):

  • Differential evolution is a stochastic parallel direct search evolution strategy optimization method that is fairly fast and reasonably robust. Differential evolution is capable of handling nondifferentiable, nonlinear, and multimodal objective functions. It has been used to train neural networks having real and constrained integer weights.
  • Nelder-Mead is a direct search method of optimization that is based on evaluating a function at the vertices of a simplex, then iteratively shrinking the simplex as better points are found until some desired bound is obtained.
  • Simulated annealing is a very effective practical algorithm (so named because it mimics the process undergone by misplaced atoms in a metal when it is heated and then slowly cooled). While this technique is unlikely to find the optimum solution, it can often find a very good solution, even in the presence of noisy data.

In this case, applying differential evolution to a set of initial police positions improves the coverage from 50% to an optimal 69%.

Coverage by six police officers before and after optimization

Mathematical covering problems

Click to animate
disk covering puzzle

Specific covering problems are also a source of mathematical investigation. One such problem is the so-called disk covering problem: given n identical disks, find the smallest possible radius r(n) such that there exists an arrangement of the disks that (just) completely covers the unit disk. Note that this is actually a different problem from the lighthouse or police coverage problems mentioned in the script, in which we are asked to assume that a shape (i.e., the California coast, or downtown Los Angeles) is of fixed size and is independent of the number of disks, and the problem posed is to find an arrangement of disks that provides optimal (or, practically speaking, as good as practically possible) coverage.

Download Interactive Computation

In the case of trying to apply a numeric algorithm to find r(n), it is necessary to reliably optimize a packing for a given radius, then vary the radius until 100% coverage can no longer be achieved. As a result, this is actually a much harder problem than covering a fixed shape optimally, especially as n increases. In fact, while the cases of n = 1 to 4 are trivial, r(5) is already quite difficult, and while its exact solution has been proved mathematically (illustrated below; it turns out to be very slightly smaller than the radius covered by five symmetrically arranged disks--the so-called five disks problem), minimal radii are not even known for almost all larger n.

disk covering problem

Scene 30:
INT. FBI - WAR ROOM - MOMENTS LATER

More-complicated heuristics

Of course, the idealized mathematical problem we set up and solved for police coverage ignored real-world considerations such as the presence of buildings, busy streets, and other obstacles; the difficulty in estimating the coverage radii for a set of police officers; and so forth. In a refinement of their initial lighthouse model, Charlie and Amita incorporate more-complicated heuristics into an algorithm with help from Larry:


LINES show up from various points, with different widths --
paths with various branches -- swaths of colored light, also
with mathematical notations -- creating loose geometric
patterns --

                     LARRY
           As we receive more data, we can
           better predict and weight possible
           travel paths... of course, it must
           look fairly abstract --

This enhanced algorithm is what ultimately allows Don to identify the subway tunnels as a likely hiding place in Scene 30:

                    DON (cont'd)
           Why do you have such low values on
           the subway stations?

                    CHARLIE
           Coverage -- there are police on the
           station stairs and platforms, others
           riding the trains back and forth...

                    DON
           ... but not the tunnels...
           (tracing the route)

And with some Hollywood magic, that's exactly where he locates Colby and Carter in Scene 31!

Scene 47:
INT. FBI - WAR ROOM - DAY

Illumination problem

In Scene 47, Charlie is attempting to determine where fugitive Carter has fled. He has an inspiration that Carter may not have run to the Chinese Embassy, but instead to a ship making its way out of U.S. territorial waters:

                    CHARLIE
           Ernest Straus posited a roomful of
           mirrors...

           ... Straus wondered if there was a
           room so complex that a match lit in
           the right place couldn't reach every
           corner?

           It was forty years before George
           Tokarsky devised an answer -- a 26
           sided room...
               (beat)
           ... and, in the spirit of that
           problem, and solution, I looked for
           Carter's dark corner -- the nearest,
           safest Chinese soil.

The general problem that Charlie refers to is known as the illumination problem, proposed in the early 1950s by Ernst Straus.

In 1958, a young Roger Penrose used the properties of the ellipse to describe a room with curved walls that would always have dark (unilluminated) regions, regardless of the position of the candle. Before we discuss this room in more detail, recall that an ellipse is an oval-shaped figure that can be defined as the set all points in a plane whose distances from two fixed points (known as the foci) sum to a positive constant, as illustrated below.

 
Click to animate
schematic diagram of an ellipse ellipse animation

Ellipses aligned along the Cartesian coordinate axes are described by the equation

x^2/a^2 + y^2/b^2=1

where a and b are, respectively, half of the major and minor axes of the ellipse, known as the semimajor axis and semiminor axis. Ellipses arise in many physical contexts, including as the shape of planetary orbits in Newton's theory of gravitation. They also have a large number of intriguing mathematical properties, including the fact that any ray of light passing through a focus and reflecting off the walls of an ellipse will pass through the other focus after a single bounce.

Penrose's room is illustrated below, and consists of two half-ellipses at the top and bottom and two mushroom-shaped protuberances (which are in turn built up from straight line segments and smaller half-ellipses) on the left and right sides. The ellipses and mushrooms are strategically placed as shown, with the red points being the foci of the half-ellipses. There are essentially three possible configurations of illumination. In this figure, lit regions are indicated in white, unilluminated regions are indicated in gray, and the position of the light source is indicated by the black cross-hairs. As can be seen, the entire room (the space within the blue border) can never be fully illuminated.

Click to animate
Penrose's unilluminable room

After Straus's question had thus been answered in the negative for arbitrarily shaped rooms, the more restrictive problem of rooms required to have walls composed of straight line segments remained open. In particular, in 1969, Victor Klee publicized these questions:

  1. Is every polygonal region illuminable from every point in the region?
  2. Is every polygonal region illuminable from at least one point in the region?

Download Interactive Computation

Both questions remained open until 1995, when George W. Tokarsky showed that unilluminable straight-walled rooms exist in two and three dimensions. Interestingly, question (2) remains open. The smallest known counterexample to (1) found by Tokarsky in two dimensions has 26 sides, and is illustrated below. It should be noted that the Tokarsky room is a borderline case, because in actuality a finite number of dark points remain unilluminated when a point light source is placed at a given position. So for an extended light source, this room actually is illuminable. The path of light beams for a number of different candle positions and beam orientations in Tokarsky's room are animated below. An even small counterexample--a room with 24 sides--was subsequently found by Castro in 1997; see MathWorld for an illustration.

Click to animate
Tokarsky's 26-sided room


Download Interactive Computation

Mathematical billiards

Illumination problems are intimately related to billiards. The reflection of light from the surface of a mirror is exactly analogous to the reflection of a billiard ball from a cushion of a billiard table because the so-called law of reflection--which states that the angle of incidence equals the angle of reflection--applies equally in both cases. There is some very interesting math involved in billiards. In fact, analysis of billiard paths can involve sophisticated use of powerful mathematical tools such as ergodic theory and dynamical systems.

Elliptical billiard tables

An interesting result in billiard-table mathematics is that on an elliptical billiard table, the envelope of a trajectory is a smaller ellipse (top left figure), a hyperbola (top middle figure), a line through the foci of the ellipse (top right figure), or a closed polygon (bottom figures). The closed-polygon case is related to a remarkable geometric result known as Poncelet's porism. An interactive exploration of the elliptical billiard table is available from The Wolfram Demonstrations Project.

Scene 58:
EXT. CALSCI FACULTY CLUB - DAY

Summing up with an equation

                     AMITA
           Sounds like an addendum to "The
           Mathematics of Friendship."
           
                     LARRY
           I'm not familiar with that paper --

                     ALAN
           Early Charles Eppes -- friendship as
           an equation...

                     DON
           ... a self-improvement manual for
           eggheads.

While Charlie, Alan, Don, Larry, and Amita could undoubtedly engage in an enlightening conversation over beer and pizza about the mathematics of billiards, they instead close this episode by discussing Charlie's work on the mathematics of friendship. We will not attempt to derive Charlie's "friendship equation" here due to limitations of space and time, but perhaps Charlie will have more to say on this topic in upcoming episodes!

References

Castro, D. "Corrections." Quantum 7, 42, Jan. 1997.

Croft, H. T.; Falconer, K. J.; and Guy, R. K. "Illumination Problems." §A5 in Unsolved Problems in Geometry. New York: Springer-Verlag, pp. 18-19, 1991.

Gardner, M. The Second Scientific American Book of Puzzles & Diversions: A New Selection. New York: Simon and Schuster, pp. 142-144, 1961.

Ingber, L. "Simulated Annealing: Practice Versus Theory." Math. Comput. Modelling 18, 29-57, 1993.

Kirkpatrick, S.; Gelatt, C. D.; and Vecchi, M. P. "Optimization by Simulated Annealing." Science 220, 671-680, 1983.

Klee, V. "Is Every Polygonal Region Illuminable from Some Point?" Math. Mag. 52, 180, 1969.

Nelder, J. A. and Mead, R. "A Simplex Method for Function Minimization." Comput. J. 7, 308-313, 1965.

Neville, E. H. "On the Solution of Numerical Functional Equations, Illustrated by an Account of a Popular Puzzle and of its Solution." Proc. London Math. Soc. 14, 308-326, 1915.

ReVelle, C. S. and Rosing, K. E. "Defendens Imperium Romanum: A Classical Problem in Military Strategy." Amer. Math. Monthly 107, 585-594, 2000.

Rubalcaba, R. R. "Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs." Ph.D. dissertation. Auburn, Alabama: Auburn University. May 13, 2005. http://webpages.uah.edu/~rubalcr/RUBALCABA.pdf

Sprott, J. C. "Dynamical Models of Love." Nonlin. Dyn., Psych., Life Sci. 8, 303-313, 2004. http://sprott.physics.wisc.edu/pubs/paper277.pdf

Sprott, J. C. "Dynamical Models of Happiness." Nonlin. Dyn., Psych., Life Sci. 9, 23-36, 2005. http://sprott.physics.wisc.edu/pubs/paper281.pdf

Tokarsky, G. W. "Polygonal Rooms Not Illuminable from Every Point." Amer. Math. Monthly 102, 867-879, 1995.

 
Wolfram: Creators of Mathematica, Leaders in Math & Computation
Wolfram|Alpha