bitonic tour
   HOME

TheInfoList



OR:

In computational geometry, a bitonic tour of a set of point sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line crosses the chain at most twice.


Optimal bitonic tours

The optimal bitonic tour is a bitonic tour of minimum total length. It is a standard exercise in
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
to devise a polynomial time algorithm that constructs the optimal bitonic tour. Although the usual method for solving it in this way takes time O(n^2), a faster algorithm with time O(n\log^2 n) is known. The problem of constructing optimal bitonic tours is often credited to Jon L. Bentley, who published in 1990 an experimental comparison of many heuristics for the
traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
; however, Bentley's experiments do not include bitonic tours. The first publication that describes the bitonic tour problem appears to be a different 1990 publication, the first edition of the textbook ''
Introduction to Algorithms ''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is ...
'' by Thomas H. Cormen,
Charles E. Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
, and
Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial In ...
, which lists Bentley as the originator of the problem.


Properties

The optimal bitonic tour has no self-crossings, because any two edges that cross can be replaced by an uncrossed pair of edges with shorter total length due to the triangle inequality. Therefore, it forms a polygonalization of the input. When compared to other tours that might not be bitonic, the optimal bitonic tour is the one that minimizes the total amount of horizontal motion, with ties broken by Euclidean distance.. For points in the plane with distinct integer x-coordinates and with real-number y-coordinates that lie within an interval of length 2\sqrt or less, the optimal bitonic tour is an optimal traveling salesperson tour.


Other optimization criteria

The same dynamic programming algorithm that finds the optimal bitonic tour may be used to solve other variants of the traveling salesman problem that minimize
lexicographic Lexicography is the study of lexicons, and is divided into two separate academic disciplines. It is the art of compiling dictionaries. * Practical lexicography is the art or craft of compiling, writing and editing dictionaries. * Theoretica ...
combinations of motion in a fixed number of coordinate directions. At the 5th
International Olympiad in Informatics The International Olympiad in Informatics (IOI) is an annual competitive programming and one of the International Science Olympiads for secondary school students. It is the second largest science olympiad, after International Mathematical Olympi ...
, in
Mendoza, Argentina Mendoza (, ), officially the City of Mendoza ( es, Ciudad de Mendoza) is the capital of the province of Mendoza in Argentina. It is located in the northern-central part of the province, in a region of foothills and high plains, on the eastern si ...
in 1993, one of the contest problems involved bitonic tours: the contestants were to devise an algorithm that took as input a set of sites and a collection of allowed edges between sites and construct a bitonic tour using those edges that included as many sites as possible. As with the optimal bitonic tour, this problem may be solved by dynamic programming..


References

{{reflist Geometric algorithms Dynamic programming