4
$\begingroup$

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the path is minimized. There is no requirement that the path return to the starting point, but must end at any other vertex besides the $n=1$ vertex. At this stage the problem is finding a Hamiltonian path through the vertexes, starting from a given point; the context I am looking has the vertexes are points in 3D space.

However, I am interested in including an additional condition -- only certain paths through vertexes are allowed, given by a coefficient $c_{ijk}$, where $c_{ijk} = 1$ if the path $i \to j \to k$ is allowed, and $c_{ijk} = 0$ otherwise. The physical context of this is to restrict the angle in 3D space between the incoming vector ${\vec r}_j - {\vec r}_i$ and the outgoing vector ${\vec r}_k - {\vec r}_j$. If this angle is greater than a fixed value $\theta_{max}$, the path cannot pass through the nodes in the sequence $i \to j \to k$. Because of this additional restriction, there is no condition on the number of paths leaving the start vertex, so that if it is impossible with a single path, multiple paths are considered.

Obviously, in the extremes where the $c_{ijk}$ are mostly zero or mostly one, there is either no solution, or the unconstrained solution is feasible, respectively. Studying the properties of $c_{ijk}$ for a given vertex can show that particular vertexes cannot be visited other than directly from the $n = 1$ vertex, or that particular edges $i \to j$ cannot be used by any path. Presumably, one could build up other such relations, but I have not gone about to find any others.

Has a system like this been previously considered in the literature, as a variation of the Hamiltonian path, or of the traveling salesman problem? If so, what is the reference?

$\endgroup$

1 Answer 1

4
$\begingroup$

This is an incomplete answer, but perhaps these key terms and references could help. Your paths are often called angle-restricted paths in the literature, e.g., Fekete and Woeginger's 1997 "Angle-Restricted Tours in the plane." This is obviously not directly relevant to your nonplanar, non-tour, but that is a key phrase. Another more recent reference is the Dumitrescu, Pach, Tóth, 2009 paper, "Drawing Hamiltonian cycles with no large angles." That again concerns planar tours, as does "Paths with No Small Angles" by Bárány, Pór, and Valtr, 2009. The general angle-restricted TSP problem in arbitrary dimensions is NP-hard, as established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."

This general area of research is called graph drawing. Here are two papers from that community that might be worth exploring: a vintage (1997) paper, "H3: laying out large directed graphs in 3D hyperbolic space," by Munzner; and a 2011 paper, "Optimal 3D Angular Resolution for Low-Degree Graphs," by Eppstein, Löffler, Mumford, and Nöllenburg. From the latter:

We show that every graph of maximum degree three can be drawn in three dimensions with at most two bends per edge, and with 120-degree angles between any two edge segments meeting at a vertex or a bend.

To give you a sense, here is their Fig.4:
     alt text

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.