In computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, a bitonic tour of a set of point

Point (geometry)

In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...

 sites in the Euclidean plane is a closed polygonal chain that has each site as one of its vertices, such that any vertical line

Line (geometry)

The notion of line or straight line was introduced by the ancient mathematicians to represent straight objects with negligible width and depth. Lines are an idealization of such objects...

 crosses the chain at most twice.

The optimal bitonic tour is a bitonic tour of minimum total length. It is a standard exercise in dynamic programming

Dynamic programming

In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...

 to devise a polynomial time algorithm that constructs the optimal bitonic tour. The optimal bitonic tour may be used as a heuristic solution to the traveling salesman problem, however its length may be larger than that of the optimal traveling salesman tour.

At the 5th International Olympiad in Informatics

International Olympiad in Informatics

The International Olympiad in Informatics is an annual computer science competition for secondary school students. The first IOI was held in 1989 in Pravetz, Bulgaria....

, in Mendoza, Argentina

Mendoza, Argentina

Mendoza is the capital city of Mendoza Province, in Argentina. It is located in the northern-central part of the province, in a region of foothills and high plains, on the eastern side of the Andes. As of the , Mendoza's population was 110,993...

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.

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.