Bitonic tour
{{Short description|Computational geometry concept}}
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 to devise a polynomial time algorithm that constructs the optimal bitonic tour.Introduction to Algorithms, 3rd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2009. Problem 15-3, p. 405.{{citation|title=The Algebra of Programming|first1=Richard S.|last1=Bird|first2=Oege|last2=De Moor|publisher=Prentice Hall|year=1997|isbn=9780135072455|page=213}}. Although the usual method for solving it in this way takes time , a faster algorithm with time is known.{{citation
| last1 = de Berg | first1 = Mark
| last2 = Buchin | first2 = Kevin
| last3 = Jansen | first3 = Bart M. P.
| last4 = Woeginger | first4 = Gerhard
| editor1-last = Chatzigiannakis | editor1-first = Ioannis
| editor2-last = Mitzenmacher | editor2-first = Michael
| editor3-last = Rabani | editor3-first = Yuval
| editor4-last = Sangiorgi | editor4-first = Davide
| contribution = Fine-Grained Complexity Analysis of Two Classic TSP Variants
| contribution-url = https://drops.dagstuhl.de/opus/volltexte/2016/6277
| doi = 10.4230/LIPIcs.ICALP.2016.5
| isbn = 978-3-95977-013-2
| location = Dagstuhl, Germany
| pages = 5:1–5:14
| publisher = Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
| series = Leibniz International Proceedings in Informatics (LIPIcs)
| title = 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
| volume = 55
| year = 2016| doi-access = free
}}
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;{{citation|last=Bentley|first=Jon L.|contribution=Experiments on traveling salesman heuristics|title=Proc. 1st ACM-SIAM Symp. Discrete Algorithms (SODA)|year=1990|pages=91–99|isbn=9780898712513 |url=http://portal.acm.org/citation.cfm?id=320186}}. 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 by Thomas H. Cormen, Charles E. Leiserson, and Ron Rivest, 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.{{citation
| last = Sourd | first = Francis
| doi = 10.1007/s10878-008-9154-0
| issue = 1
| journal = Journal of Combinatorial Optimization
| mr = 2579501
| pages = 1–15
| title = Lexicographically minimizing axial motions for the Euclidean TSP
| volume = 19
| year = 2010| s2cid = 42168298
}}.
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.{{citation
| last1 = Alkema | first1 = Henk
| last2 = de Berg | first2 = Mark
| last3 = Kisfaludi-Bak | first3 = Sándor
| editor1-last = Cabello | editor1-first = Sergio
| editor2-last = Chen | editor2-first = Danny Z.
| contribution = Euclidean TSP in Narrow Strips
| contribution-url = https://drops.dagstuhl.de/opus/volltexte/2020/12162
| doi = 10.4230/LIPIcs.SoCG.2020.4
| isbn = 978-3-95977-143-6
| location = Dagstuhl, Germany
| pages = 4:1–4:16
| publisher = Schloss Dagstuhl–Leibniz-Zentrum für Informatik
| series = Leibniz International Proceedings in Informatics (LIPIcs)
| title = 36th International Symposium on Computational Geometry (SoCG 2020)
| volume = 164
| year = 2020| doi-access = free
| s2cid = 219554488
}}
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 combinations of motion in a fixed number of coordinate directions.
At the 5th International Olympiad in Informatics, in Mendoza, Argentina 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.[http://olympiads.win.tue.nl/ioi/ioi93/index.html IOI'93] contest problems and report.{{citation|title=The Canadian Airline Problem and the Bitonic Tour: Is This Dynamic Programming?|first=Pedro|last=Guerreiro|date=December 2003|publisher=Departamento de Informática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa|url=https://www.researchgate.net/publication/228391119}}.