Given a sequence of k convex polygons in the plane, a start point s, and a target point t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. We revisit this touring polygons problem, which was introduced by Dror et al. (STOC 2003), by describing a simple method to compute the so-called last step shortest path maps, one per polygon. We obtain an O(kn)-time solution to the problem for a sequence of pairwise disjoint convex polygons and an O(k2n)-time solution for possibly intersecting convex polygons, where n is the total number of vertices of all polygons. A major simplification is made on the operation of locating query points in the last step shortest path maps. Our results improve upon the previous time bounds roughly by a factor of log n.

Let α and β be polygons with the same area. A Dudeney dissection of α to β is a partition of α into parts which can be reassembled to produce β in the following way. Hinge the parts of α like a chain along the perimeter of α, then fix one of the parts and without turning the pieces over, rotate the remaining parts about the fixed part to form β in such a way that the entire perimeter of α is in the interior of β and the perimeter of β consists of the dissection lines formerly in the interior of α . In this paper we discuss a special type of Dudeney dissection of convex polygons in which α is congruent to β and call it a congruent Dudeney dissection. In particular, we consider the case where all hinge points are interior to the sides of the polygon α. A convex polygon which has a congruent Dudeney dissection is called a chameleon. We determine all convex polygons which are chameleons.