Convex Polygons How to reason about this polygon? Convex hu Complexity? Minimum Covering Minimum Partitioning 7 triangles 12 triangles Complexity? Type Rectangl O(NlogN) Complexi Configuration Space The set of legal configurations of the robot Size of C-space depends on degrees of freedom of robot 3-d C-Space e=/2 0=0 A A and B are convex polygons. a is a free-flying object C is represented by parameterizing each configuration q by (xy)∈Rx[0,2 The represented C-obstacle is a volume bounded by patches of ruled surfaces Image adapted from J C LatombeConvex Polygons How to reason about this polygon? Minimum Covering: 7 triangles Complexity? Convex Hull Complexity? Minimum Partitioning: 12 triangles Complexity? Type Holes Complexity Convex Polygons Y NP-Hard Convex Polygons N O(N3 ) Rectangles Y O(N3/2logN) Rectangles N O(N) Triangulation Y O(NlogN) Configuration Space ● The set of legal configurations of the robot ● Size of C-Space depends on degrees of freedom of robot A and B are convex polygons. A is a free-flying object. C is represented by parameterizing each configuration q by (x,y, ) R2x [0,2 ]. A A B B y y y x x x The represented C-obstacle is a volume bounded by patches of ruled surfaces. 3-d C-Space q= /2 q p q =0 q ∈ p Image adapted from J. C. Latombe