Computational Geometry Lecture Notes: Minkowski Sums and C-Obstacles Overview
Explore the definition, complexity, computation, and application of Minkowski Sums and C-obstacles in computational geometry with detailed examples and theorem proofs. Understand the concepts of translational motion planning and negation of sets for efficient algorithm design.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Minkowski Sums Outline: I. Definition II. C-obstacles III. Complexity of the sum of two convex polygons IV. Computation V. Non-convex robot or obstacle VI. Translational motion planning Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.
C-obstacle for a Translational Robot Robot ? Obstacle ? C-obstacle ?? ?(?,?) configuration ?(0,0) collision ?? = ?,? ?(?,?) ? } The boundary of ?? is traced out by the reference point of ? as it slides along the boundary of ?.
I. Minkowski Sum Hermann Minkowski (1864-1909) Albert Einstein was his former student. Two sets ?1,?2 2 ?1 ?2= ? + ? ? ?1,? ?2} ?1= 1,2 ,?2= 3,0 1 + 3 = 2 1 + 0 =1 2 + 3 = 1 2 + 0 = 2 ?1 ?2= { 2, 1,1,2} * Image from Hermann Minkowski Wikipedia.
Minkowski Sum of 1D Sets ?1= 3,0 ,?2= 1,2 ?1 ?2 3 0 1 2 ?1 ?2 2 0 2
Minkowski Sum of 2D Sets ?1 ?2= ? + ? ? ?1,? ?2} ?2 ?1 ?2 ?1
Negation of a Set ? = ??,?? ? = ( ??, ??) A set ?: ? = ? ? ?} ? ?
II. Formula for C-obstacle Theorem 1 The C-obstacle ?? of ? is ? ? 0,0 . = ?, ? ?,? ?(0,0)} Proof ( ) Suppose (?,?) ??, i.e., ?(?,?) intersects ?. We need to show (?,?) ? ( ? 0,0 ). ? Let ? = (??,??) be a point in the intersection. ? ?(?,?) (?? ?,?? ?) ?(0,0) ? ? ?(?,?) ??+ ?, ??+ ? ?(0,0) (?? ?,?? ?) ? ? ? ?(0,0) ? + ??+ ?, ??+ ? = (?,?) ? ( ? 0,0 )
Proof (contd) ( ) Let (?,?) ? ( ? 0,0 ). There exists (??,??) ?(0,0) and (??,??) ? such that ?,? = ??,?? + ??, ?? = (?? ??,?? ??) ??= ??+ ? and ??= ??+ ? ? (??,??) ?(0,0) (??,??) (??,??) ?(?,?) ? (?,?) (??,??) ? (??,??) (??,??) ? ?(?,?) ? (0,0) ?(?,?) intersects ?, i.e., (?,?) ??.
Verification via an Example Two equivalent ways of C-obstacle construction: Straightforward via Minkowski sum ? ( ? 0,0 ) ? ? ? ? ? ? ?(0,0) ?(0,0)
III. Extreme Points Two polygons ? and ?. ?: an extreme point on ? in the direction ?, that is, ? ? ? ? for any ? ?. ? + ? ? ? ? ? ? ?: an extreme point on ? in the direction ?, that is, ? ? ? ? for any ? ?. ? ? Any point ? ? ? has ? = ? + ? for some ? ? and ? ?. ? ? = (? + ?) ? (? + ?) ? ? + ? is an extreme point in the direction ? on ? ?. An extreme point in the direction ? on ? ? is the sum of two extreme points in ? on ? and ?, respectively.
Minkowski Sum of Convex Polygons ? ? ? ? Theorem 2 Let ? and ? be two convex polygons with ? and ? edges, respectively. Then ? ? is a convex polygon with ? + ? edges.
Complexity of Minkowski Sum ?? ProofConvexity of the Minkowski sum of two convex sets follows from the definition. ? = ? ? ? ? ? To bound the complexity, consider an edge ? of ? ?. ? ? ? ??: outward normal of ?. ? must be generated by points on ? and ? that are extreme in ??. At least one of ? and ? must have an edge extreme in ??. Without loss of generality, this edge is, say, ? on ?. Charge ? to ? . Every edge of ? and ? is charged at most once. # edges of ? ? ? + ?. The upper bound ? + ? is achieved if ? and ? have no parallel edges.
IV. Computation of the Minkowski Sum Compute ? ? when ? and ? are convex. Brute-force algorithm Compute ? + ? for each pair (?,?) of vertices with ? ? and ? ?. Construct the convex hull of all the sum vertices. ?(?? log? + log? )
Faster Computation Idea: Look at a pair of vertices that are extreme in the same direction. ?(?3,?4) ?(?1,?2) ?(?4,?1) ?4 ?1 ?3 ?2 ? ?1 ? ?(?3,?1) ?(?2,?3) ?(?1,?2) ?(?2,?3) ?2 ?3 Represent all the directions by a unit circle. ?(?1,?2) ?4 interval of directions in which ?2 is extreme ?1 ?3 ?2 ?1 ?(?3,?1) ?(?2,?3) ?2 ?3
Extreme Pairs Superpose the two partitioning. ?4 ?1 ?2 ?1 ?3 ?3 ?2 (?1,?4) (?2,?4) (?1,?3): interval of directions in which ?1 and ?3 are extreme in ? and ?, respectively. This works like the merge step of merge sort! (?2,?1) (?3,?3) (?3,?1) (?3,?2)
The Algorithm MinkowskiSum(?, ?) // ?1, ,?? and ?1, ,?? in counterclock- // wise order with ?1 and ?1 having the // smallest ?-coordinate 1. ? 1;? 1 2. ??+1 ?1;??+2 ?2;??+1 ?1;??+2 ?2 3. repeat 4. add ??+ ?? as a vertex to ? ? 5. if angle(??,??+1) < angle(??,??+1) // case 1 6. then ? ? + 1 7. ... ?? ??+1 ?? ??+1 ??+1?? ?? angle made by ????+1 with the ?-axis ??+1 (??,??) (??+1,??)
Case 2 MinkowskiSum(?, ?) 1. 2. 3. repeat 4. add ??+ ?? as a vertex to ? ? 5. if angle(??,??+1) < angle(??,??+1) 6. then ? ? + 1 7. else if angle ??,??+1 > angle(??,??+1) // case 2 8. then ? ? + 1 9. ... ? 1;? 1 ??+1 ?1;??+2 ?2;??+1 ?1;??+2 ?2 ?(??,??+1) ?? ??+1 ?? ?(??,??+1) ??+1 (??,??) (??,??+1)
Case 3 MinkowskiSum(?, ?) 1. 2. 3. repeat 4. add ??+ ?? as a vertex to ? ? 5. if angle(??,??+1) < angle(??,??+1) 6. then ? ? + 1 7. else if angle ??,??+1 > angle(??,??+1) 8. then ? ? + 1 9. else ? ? + 1; ? ? + 1 // case 3 10.until ? = ? + 1 and ? = ? + 1 ? 1;? 1 ??+1 ?1;??+2 ?2;??+1 ?1;??+2 ?2 ? ??,??+1 = ?(??,??+1) ??+1,??+1 ??,?? (??,??) (??+1,??+1) Running time ?(? + ?)
V. Nonconvex Robot or Obstacle Triangulate whichever is nonconvex. Suppose both are nonconvex and triangulated into ?1, ?? 2 and ?1, ?? 2, respectively. ? 2 ? 2 ? = ?? ? = ?? ?=1 ?=1 Make use of the following equality for three sets ?1,?2 and ?3: ?1 ?2 ?3 = (?1 ?2) (?1 ?3)
Complexity of ? ? Both ? and ? are nonconvex. Union of ?(??) polygons of complexity ?(1) ? 2 ? 2 ? ? = ?? ?? ?=1 ?=1 ?(?2?2) //tight in the worst case ? is convex but ? is not. ? 2 Union of ?(?) pseudodisks (every pair defines 2 boundary crossings) ? ? = ? ?? ?=1 ? is not convex but ? is. ?(??) ? 2 ? ? = ?? ? ?(??) ?=1
VI. Translational Motion Planning We are given the robot ? with constant complexity; a set of obstacles with total complexity ?(?). ?1,?2, ,??: the triangles from triangulating the obstacles. Forbidden configuration space ? ? ?????= ???= ?? ( ? 0,0 ) ?=1 ?=1 Complexity ?(?)
Computing the Forbidden C-Space Divide-and-conquer ? 2 1 1. ????? ?=1 ??? ? 2 2. ????? ?=? ??? 2+1 1 2 3. Compute ?????= ????? ????? overlay of planar subdivisions ?(?log?) ? ? : time of computation ? 2 ? ? = ?(?log2?) ? ? = 2? + ?(?log?) ????? is the complement of ?????. It has complexity ?(?).
Time Complexity for Path Planning Theorem 3????? can be computed in time ?(?log2?). Next, compute a trapezoidal map of ????? in ? ?log? expected time. Total preprocessing time: ?(?log2? + ?log?)=?(?log2?) Theorem 4 Translational motion planning for a convex robot of ?(1) complexity among polygonal obstacles of ?(?) total complexity can be solved in ?(?) time with preprocessing in ?(?log2?) expected time.
