COMP 4202/5204 Assignment 1

2025-02-26 Admin 写评论


Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due


COMP 4202/5204 Assignment 1

Must be handed in no later than February 26th before 23:59. Your assignment should be submitted online on Brightspace as a single .pdf file. The filename should contain your name and student number. No late assignments will be accepted. You can type your assignment or you can upload a scanned copy of it. Please, use a good image capturing device. Make sure that your upload is clearly readable. If it is difficult to read, it will not be graded.

Question 1: 20 points

• Show via a set of illustrations and comments how the randomized incremental Delaunay triangulation (discussed in class) works on the point-set listed below. (If steps are repeated and have already been illustrated sufficiently you may skip their illustration.)
• How would you compute, in general, the outer triangle (here this is already given through the point set)?
• You must use as insertion order, the order given by the indices of the points. If you were not given this insertion order, what would you have to do?
• Indicate clearly also how the point location procedure is carried out at each insertion.

Question 2: 20 points

Construct a best-case and a worst-case example for the above algorithm. The construction mustbe clear and show how the cases are generalized to an infinite sequence of input points. This needs to be done without consulting the literature; otherwise, plagiarism rules will be evoked.
Question 3: 30 points

You are given two planar subdivisons as per figure. Compute the overlay and the topology using the algorithm presented in class. Illustrate the steps the algorithm takes. Make sure that you are carrying out ALL steps of the overlay procedure!

Question 4: 20 points

A fancy museum (whose floorplan is given by a simple polygon) has installed some laser sensors to prevent robberies. Two laser sensors are connecting if they are horizontally visible (inside the polygon). That means the horizontal line-segment joining the two sensors is not intersected by a museum wall (i.e., by an edge of the floorplan polygon. Again we only care about sensor visiblity inside.). Let m be the number of sensors and n be the number of polygon edges. Design an efficient algorithm for finding all pairs of connecting sensors, analyze its time complexity in terms of m and n. Argue why your algorithm is correct. As always, the better the algorithm the better the mark. You may use any algorithm discussed in class.

Question 5: 20 points 

Carleton wants to help students who have mobility issues (say a broken leg, ...). These students need to get from buildung A to buildung B, or to the O-train, bus, to their private cars... respecting their abilities. Design a GIS-based system to help those students.

  • List all relevant queries
  • List all data that need to be collected to answer these. Invstigate where you might get them from.
  • List all algorithms that need to be implemented/found/designed in this context

Question 6: 15 points GRADUATE STUDENTS - only

Describe and illustrate the algorithms to compute the dual going from VD to DT and from DT to VD. Suppose someone gives you a Voronoi diagram and forgets to give you the input point set.

Can you always uniquely reconstruct that missing point set? If not, are there conditions on the VD that makes the reconstruction unique?

End of Assignment 1.

发表评论

电子邮件地址不会被公开。 必填项已用*标注