In
computational geometry, a bitonic tour of a set of
point sites in the
Euclidean plane
In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
is a
closed polygonal chain
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its Vertex (geometry), vertices. The curve itself consists of th ...
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 to devise a
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
algorithm that constructs the optimal bitonic tour. Although the usual method for solving it in this way takes time
, a faster algorithm with time
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
In the theory of computational complexity, the travelling salesman problem (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 city exac ...
; 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, Ron Rivest, Ronald L. Rivest, and Clifford Stein. The book is described by its publisher as "the leading algorithms text in universities w ...
'' by
Thomas H. Cormen,
Charles E. Leiserson, and
Ron Rivest
Ronald Linn Rivest (;
born May 6, 1947) is an American cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity.
He is an Institute Profess ...
, 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
-coordinates and with real-number
-coordinates that lie within an interval of length
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 the art of compiling dictionaries. It is divided into two separate academic disciplines:
* Practical lexicography is the art or craft of compiling, writing and editing dictionaries.
* Theoretical lex ...
combinations of motion in a fixed number of coordinate directions.
At the 5th
International Olympiad in Informatics, in
Mendoza, Argentina
Mendoza (), officially the City of Mendoza (), is the capital of the Provinces of Argentina, province of Mendoza Province, Mendoza in Argentina. It is located in the northern-central part of the province, in a region of foothills and high plain ...
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