0
$\begingroup$

There are dotes on the plane $(x,y)$ connected with directed edges. The distance $\rho(A,B)$ is standard euclidean: $|\overrightarrow{AB}|$. Except the distance cost we pay for rotation: $k\alpha$, $\alpha$ is the angle. We need to find the shortest ("cheapest") path between to vertexes $s,\,t$.

It's sad, but triangle inequality doesn't hold true anymore. I think about smth like launching BFS from $s$ and keeping for each vertex a list of pairs (predecessor, distance). It's just an idea and I'm not sure if it'll work. Maybe it's a well known problem?

1 Answers 1

2

You could replace each vertex $v$ by vertices $v_e$, one for each edge $e$ incident at $v$, with $e$ now incident at $v_e$ instead, and connect all pairs of vertices $v_e$, $v_f$ by edges reflecting the rotation cost. Or you could reduce the number of edges by only connecting $v_e$ and $v_f$ if $e$ and $f$ are at adjacent angles. For $s$ and $t$, you could either leave them unchanged, or, if that's simpler, treat them like all other vertices and then add new vertices s', t' with zero-cost edges to all the vertices that $s$ and $t$ were replaced by. In any case, the problem becomes a standard problem of finding the shortest path in the resulting graph.

  • 0
    Ca$n$ you explain the trick with adjacent angles, I don't clearly understand how it works and what's more important why it works.2012-03-29