Solution 1 Introduction to Computational Geometry 50 473 56 573 Spring 2016 Homework Due Date 4 4 13 2016 321 BSB Professor E mail Phone Suneeta
Solution Introduction to Computational Geometry Spring Homework Due Date BSB Professor
Solution Introduction to Computational Geometry Spring Homework Due
to Computational Geometry Spring Homework Due Date BSB Professor E mail Phone Suneeta
Solution Introduction to Computational Geometry Spring Homework
Due Date BSB Professor E mail Phone Suneeta
Solution Introduction to Computational Geometry
Solution Introduction
(Solution) 1 Introduction to Computational Geometry 50:473/56:573 (Spring 2016) Homework: Due Date: 4 4/13/2016 321 BSB Professor: E-mail: Phone: Suneeta...

 Category: General Words: 1050 Amount: \$12 Writer:

Paper instructions

computational geometry................/............................1 Introduction to Computational Geometry 50:198:473/56:198:573 (Spring 2016) Homework: 4 Due Date: 4/13/2016 Ofce: 321 BSB ProFessor: Suneeta Ramaswami E-mail: [email protected] URL: http://crab.rutgers.edu/~rsuneeta Phone: (856)-225-6439 Homework Assignment 4 Give written (and legible) answers to the following questions. Please give succinct and mathe- matically precise answers. Whenever you are asked to give an algorithm for a problem, you should present the following: the algorithm, a justiFcation of its correctness, and a derivation of its run- ning time. Write clear and convincing pseudo-code for your algorithms. All work must be done independently. I. (30 points) We studied a randomized incremental algorithm for constructing the trapezoidal decomposition. Recall that the geometric structure of the Fnal trapezoidal decomposition is always the same, regardless of the order in which the segments are inserted. However, there are instances of probabilistic constructions in which the Fnal geometric structure depends on the particular order in which the objects are inserted. In this question, you will study one such structure called the Binary Space Partition (BSP). You are given a set of n non intersecting line segments in the plane, and you build a subdivision recursively as follows: Initially, the subdivision contains no segments and only one face, the entire space. When the Frst segment is inserted, this face is partitioned into two faces by a splitting line that contains this segment. In general, as each segment is added, every face of the existing subdivision that intersects this segment is split by the line containing the segment. An example is shown in ±igure 1. In (a), the order of insertion is s 1 ,s 2 ,s 3 ,s 4 ,s 5 . In (b), the order of insertion is s 4 ,s 5 ,s 3 ,s 1 ,s 2 . Observe that di²erent orders of insertions of the segments result in di²erent subdivisions. When a splitting line is added, each future segment which intersects this splitting line is said to be cut by the line. (Therefore, if we say that a segment v is cut by a splitting line containing u , then v must have been inserted after u .) In ±igure 1(a), segment s 3 is cut by the line extending segment s 1 , and segments s 3 and s 5 are cut by the line extending s 2 . Note that segment s 1 is not considered to be cut by s 2 (because s 2 was inserted after s 1 ). 1. Given n segments in general position, prove that the number of faces of the Fnal BSP subdivision is equal to n + 1 plus the total number of cuts (verify this in the Fgure above). Hint: Use induction. 2. Give an example of a set of n nonintersecting line segments such that for one insertion order, the resulting BSP has size O ( n ) and for another insertion order, the BSP has size ?( n 2 ). 3. Given two line segments u and v , deFne index ( u,v ) as follows: If the line containing u does not intersect v , then index ( u,v ) = ? . Otherwise, deFne the index to be the number of line segments that intersect this line and lie between v and the closest endpoint of u . (In the Fgure below, index ( u,v ) = 3. In ±igure 1(a), index ( s 2 ,s 5 ) = 1, and index ( s 1 ,s 3 ) = 0.) Prove that if the segments are inserted in random order, then the probability that u cuts v is at most 1 index ( u,v )+2 .