Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
I'm afraid the resulting graph will be too big. Is it possible to estimate the number of vertexes after replacement? – Igor Mar 28 '12 at 13:59
@Igor: Sure, the number of vertices after replacement is twice the number of edges before replacement. If you do the variant where you only add between new vertices corresponding to edges at adjacent angles, there's one new edge for every new vertex, so the total number of edges after replacement is three times the number of edges before replacement. – joriki Mar 28 '12 at 14:40
Can you explain the trick with adjacent angles, I don't clearly understand how it works and what's more important why it works. – Igor Mar 29 '12 at 20:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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