A Note on the Aspect Angle Formed between the Convex Hull and its Interior Points, in the Context of the Euclidean Traveling Salesman Problem,
Abstract
For the Euclidean traveling salesman problem (ETSP), it has long been known that the relative order of the cities comprising the convex hull is preserved within an optimal tour. It is thus during ETSP problem solving to utilize the hull as an initial tour. The main result of this paper is an extension of this concept, which proves that all interior cities which form a disjoint maximally obtuse angle with the convex hull may also be inserted into the baseline tour (a disjoint, maximally obtuse angle is one larger than any other obtuse angle which a city may form with the hull). Furthermore, any cities which form a disjoint, maximally obtuse angle with the resultant structure may also be inserted. The only caveat is that each city inserted in this fashion must be periodically retested, to check that the maximally obtuse condition remains valid. The geometric rationale for the technique was developed in an earlier paper, in which it was shown that passing through each hull vertex is a hyperbola the purpose of which is to discriminate the specific hull segment to be perturbed when inserting a city into the tour. With regard to performance, the entire process just described may be achieved in a preprocessing step with time complexity O(n log n), where n is the number of cities being processed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1992
- Accession Number
- ADP006590
Entities
People
- T. M. Cronin