Bitonic tour
From Wikipedia, the free encyclopedia
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.
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.[1] 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.[2]
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 constructed 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.[3]
[edit] References
- ^ Introduction to Algorithms, 2nd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2001. Problem 15-1, p. 364.
- ^ Bentley, Jon L. (1990), “Experiments on traveling salesman heuristics”, Proc. 1st ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 91–99, <http://portal.acm.org/citation.cfm?id=320186>.
- ^ IOI'93 contest problems and report.
 |
This geometry-related article is a stub. You can help Wikipedia by expanding it. |
