Publication

Abstract : Given a set P of n points in Rd, a tour is a closed simple path that covers all the given points, i.e. a Hamiltonian cycle. % In P if no three points are collinear then the points are said to be in general position. A \textit{link} is a line segment connecting two points and a rectilinear link is parallel to one of the axes. The problems of defining a path and a tour with minimum number of links, also known as Minimum-Link Covering Path and Minimum-Link Covering Tour respectively are proven to be NP-hard in R2. The corresponding rectilinear versions are also NP-hard in R2. A set of points is said to be in \textit{general position} for rectilinear versions of the problems if no two points share any coordinate. We call a set of points in Rd to be in \textit{relaxed general position} if no three points share any coordinate and any two points can share at most one coordinate. That is, if the points are either in general position or in relaxed general position then an axis parallel line can contain at most one point. If points are in relaxed general position then these problems are NP-hard in R10. We prove that these two problems are in fact NP-hard in R4. If points in Rd, d>1 are in general position then the time complexities of these problems, both basic and rectilinear versions, are unknown.