A straight-line drawing δ of a planar graph G need not be plane but can be made so by untangling it, that is, by moving some of the vertices of G. Let shift(G,δ) denote the minimum number of vertices that need to be moved to untangle δ. We show that shift(G,δ) is NP-hard to compute and to approximate. Our hardness results extend to a version of 1BendPointSetEmbeddability, a well-known graph-drawing problem. Further we define fix(G,δ)=n−shift(G,δ) to be the maximum number of vertices of a planar n-vertex graph G that can be fixed when untangling δ. We give an algorithm that fixes at least $\sqrt{((\log n)-1)/\log\log n}$ vertices when untangling a drawing of an n-vertex graph G. If G is outerplanar, the same algorithm fixes at least $\sqrt{n/2}$ vertices. On the other hand, we construct, for arbitrarily large n, an n-vertex planar graph G and a drawing δ G of G with $\ensuremath {\mathrm {fix}}(G,\delta_{G})\leq \sqrt{n-2}+1$ and an n-vertex outerplanar graph H and a drawing δ H of H with $\ensuremath {\mathrm {fix}}(H,\delta_{H})\leq2\sqrt{n-1}+1$ . Thus our algorithm is asymptotically worst-case optimal for outerplanar graphs.

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any ε > 0, we compute a rigid motion such that the area of overlap is at least 1 - ε times the maximum possible overlap. Our algorithm uses O(1/ε) extreme point and line intersection queries on P and Q, plus O((1/ε2) log(1/ε)) running time. If only translations are allowed, the extra running time reduces to O((1/ε) log(1/ε)). If P and Q are convex polygons with n vertices in total, the total running time is O((1/ε) log n + (1/ε2) log(1/ε)) for rigid motions and O((1/ε) log n + (1/ε) log(1/ε)) for translations.

We consider searching problems in robotics that a robot has to find a path to a target by traveling in an unknown starshaped polygon P. The goal is to minimize the ratio of the distance traveled by the robot to the length of the shortest start-to-target path.Let s be a starting point in P. We first present a competitive strategy to find a path from s to the closest kernel point k of P. The length of the path that the robot generates is less than 1 + 2W (< 3.829) times the distance from s to k, which improves the best previous bound 5. 331 [3].Second, given a specified target t in P, we present a competitive strategy to find a path from s to t whose length does not exceed 17 times the length of the shortest s-t path.