Given a robot and set of obstacles, find the shortest path from $s$ to $t$ without collision.

Robot without collision volume

Starting from a point $s$ and finds a possible way to the end point $t$.

First, build a rectangle boundary and do the planar subdivision, pick the mid point for vertical planar edge and pick the mid point for ever face.

Find the shortest path from the face $f_s$ containing $s$ to that $f_t$ containing $t$. Add an edge from $s$ to the nearest face middle point and add an edge from that to $t$.

Analysis:

Creating trapezoidal map: $O(n\log n)$ time.

Locating trapezoids containing $s$ and $t$: $O(\log n)$ time.

Computing path using BFS: $O(V+E)=O(n)$ time.

Robot with polygon shape

Considering the robot has certain polygon shape in vertical direction, which means the robot polygon are not allowed to rotate in inclined angle, below repeated polygon is the robot:

The dark grey area is the open obstacle (boundary can be touched) and the light grey area is the collision area for the robot gravity, which means, if the robot gravity is located inside the light grey area, then the robot would collide the obstacle. The white area is the free space.

How we represent such structure?

Define:

• $\mathcal{R}:$ polygon robot. Reference point is $(0,0)$.
• $\mathcal R(x,y):=\mathcal R+(x,y)$, translation by vector $(x,y)$.
• $\mathcal P$: polygon obstacle.
• $\mathcal{CP}=\mathcal P\oplus(-\mathcal R)$. Here $A\oplus =\{a+b\mid a\in A,b\in B\}$ is the Minkowsky sum.

How do we compute the free space? How complicated can the space be? i.e., how many corners can it have?

Naïve algorithm

Each edge of $A\oplus B$ stems from an edge of $A$ or $B$ (or both). Therefore, $A\oplus B$ has $\leq n+m$ edges, where $n$ edges of $A$ and $m$ edges of $B$.

Compute $C_A\oplus C_B$ and take the convex hull, $C_A$ and $C_B$ are the corners of $A$ and $B$.

Time: $O(mn\log (mn))$.

For every corners $b\in B$, it will match all corners $a\in A$, thus the total number of nodes on boundary of the polygon equals to $mn$ and determining a convex hull for a polygon is $CH(P)$.

Smarter algorithm

Pick two extreme points on the polygon along the arrow direction. Move the edge $e_A$ parallel to make it ends in $B$. Then rotate the arrow and find next perpendicular edge in two polygons and remove the corresponding edge next to the boundary of forbidden area.

Time: $O(m+n)$.

Theorem $A$ and $B$ polygons with $m$ and $n$ corners,

• $A$ and $B$ are convex: $A\oplus B$ has $O(m+n)$ corners,
• only one is convex: $A\oplus B$ has $O(mn)$ corners,
• none is convex: $A\oplus B$ has $O(m^2n^2)$ corners.

These bounds are tight.

---

Defintiion Polygon $o_1$ and $o_2$ are pseudodisks iff $\partial o_1\cap int (o_2)$ and $int(o_1)\cap \partial o_2$ are connected, ($\partial o_1$ is the boundary of $o_1$ and $int(o_2)$ represents the intersection area of $o_1$ with $o_2$).

If two polygons have no intersection, they are pseudodisks as well, because the union is empty represents there is no element violates the rule.

Theorem A set of pairwise pseudodisks with $n$ corners in total $\Longrightarrow$ union has $2n$ corners.

Proof

Pay 1 means 1 corner has been introduced.

Theorem $\mathcal R$ robot with $O(1)$ corners, obstacles with $n$ corners $\Longrightarrow$ free space has $O(n)$ corners.

Proof Since there are $O(n-2)=O(n)$ triangles for a polygon with $n$ corners, then for each triangle $T_i$, the intersection $T_i\oplus(-\mathcal R)$ has complexity $O(3+O(1))=O(1)$ corners.

Since $T_i$ and $T_j$ are interior-disjoint triangles, then $T_1\oplus (-\mathcal R)$ and $T_2\oplus(-\mathcal R)$ are pseudodisks.

Finally, $\bigcup_T(T\oplus(-\mathcal R))$ has $O(n)$ corners.

Algorithm

$k$ obstacles with $n_1,\cdots,n_k$ corners, in total $n$.

Triangulating:

$$ \sum_{i=1}^kO(n_i\log n_i)=O(\sum_{i=1}^kn_i\log n_i)\leq O(\log n\sum_{i=1}^kn_i)=O(n \log n) $$

Computing Minkowsky sum between each obstacles and robot, $\mathcal{CP}_j=\mathcal P_j\oplus(-\mathcal R):O(1)$ time (three corners per $\triangle$ and one corner per robot, constant number in total), in total $O(n)$.

Below algorithm computing the forbidden space:

Compute the union of two polygons in step 5 takes $O(n\log n)$ time using overlay algorithm from chap. 2.

The total Running time: $T(n)=2T(n/2)+O(n\log n)$, solves to $T(n)=O(n\log^2n)$.

Shortest path

The complexity of computing visibility graph (for every node $i$, rotate a ray starting from $i$ and catch the intersections):

• Initialization: sort corners by angle, $O(n\log n)$ time.
• Compute intersections with horizontal sweep line and sort them by $x$-coordinate, $O(n\log n)$ time.
• Perform the rotational sweep, $O(n\log n)$ time.
• Do it for all $n$ corners, $O(n^2\log n)$

Complete algorithm for the shortest path:

• Compute visibility graph: $O(n^2\log n)$ time. $O(n)$ vertices and $O(n^2)$ edges.
• Find shortest path using Dijkstra: $O(n\log n+n^2)=O(n^2)$.
• In total $O(n^2\log n)$.

Thomas Men

$\int_{birth}^{death}\text{study} dt = \text{life}$