Strong Orientation - Application To Traffic Control

Application To Traffic Control

Robbins (1939) introduces the problem of strong orientation with a story about a town, whose streets and intersections are represented by the given graph G. According to Robbins' story, the people of the town want to be able to repair any segment of road during the weekdays, while still allowing any part of the town to be reached from any other part using the remaining roads as two-way streets. On the weekends, all roads are open, but because of heavy traffic volume, they wish to convert all roads to one-way streets and again allow any part of town to be reached from any other part. Robbins' theorem states that a system of roads is suitable for weekday repairs if and only if it is suitable for conversion to a one-way system on weekends. For this reason, his result is sometimes known as the one-way street theorem.

Subsequently to the work of Robbins, a series of papers by Roberts and Xu modeled more carefully the problem of turning a grid of two-way city streets into one-way streets, and examined the effect of this conversion on the distances between pairs of points within the grid. As they showed, the traditional one-way layout in which parallel streets alternate in direction is not optimal in keeping the pairwise distances as small as possible. However, the improved orientations that they found include points where the traffic from two one-way blocks meets itself head-on, which may be viewed as a flaw in their solutions.

Read more about this topic:  Strong Orientation

Famous quotes containing the words application to, application, traffic and/or control:

    “Five o’clock tea” is a phrase our “rude forefathers,” even of the last generation, would scarcely have understood, so completely is it a thing of to-day; and yet, so rapid is the March of the Mind, it has already risen into a national institution, and rivals, in its universal application to all ranks and ages, and as a specific for “all the ills that flesh is heir to,” the glorious Magna Charta.
    Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)

    It would be disingenuous, however, not to point out that some things are considered as morally certain, that is, as having sufficient certainty for application to ordinary life, even though they may be uncertain in relation to the absolute power of God.
    René Descartes (1596–1650)

    Poems stirred
    into paper coffee-cups, eaten
    with petals on rye in the
    sun—the cold shadows in back,
    and the traffic grinding the
    borders of spring ...
    Denise Levertov (b. 1923)

    Why wont they let a year die without bringing in a new one on the instant, cant they use birth control on time? I want an interregnum. The stupid years patter on with unrelenting feet, never stopping—rising to little monotonous peaks in our imaginations at festivals like New Year’s and Easter and Christmas—But, goodness, why need they do it?
    John Dos Passos (1896–1970)