| Shortest Tour of a Sequence of Disjoint Segments in L1 (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract Given a sequence s1,..., sK of K disjoint segments in the plane, a start point s and a target point t, we seek a path, that starts at s, visits in order each of the segments, and ends at t, such that the L1 length of the path is minimized. We give an O(K 2) algorithm that builds a data structure of size O(K) such that the shortest path, visiting k first segments in the sequence, to any point in the plane can be output in O(k) time. Related work In [2] Dror et al. solved the problem in the Euclidean metric. The touring problem can be formulated as a convex optimization program — [3] uses conic programming to find optimal tours in R d. Definitions and notation We say that a path π visits the sequence s1,..., sK if it starts at s and there exist points p1 ∈ s1,..., pK ∈ sK such that p1,..., pK appear in order along π. Let pk denote the first point of π (i.e., the point closest to s along | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||