Comp 4202 Assignment 2
Must be handed in no later than. Your assignment should be
submitted online on Brightspace as a single .pdf file. The filename should contain your name and
Copyright By PowCoder代写 加微信 powcoder
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 2-d rangetree discussed in class works
on the point-set listed below. Show the data structure in sufficient detail. You assign your
own coordinates (consistent with the picture).
• Illustrate a query operation.
• How would you extend this to 3-d?
• What would be a realistic use-case in 3-d?
• State the time and space complexities for construction of the data structure in 2-d, 3-d, as
well as the query times.
Question 2: 20 points
For the given triangulation illustrate Hoppe’s algorithm. As Energy function (i.e., here function
to select which edge to collapse) take the edge that minimizes the sum of the errors of each of its
endpoints. The error of an endpoint is the absolute value of the distance between the current
endpoint and its approximation in the new triangle. We then want to do selective refinement. You
assign (x,y,z) coordinates for the point set in (true) 2.5-d consistent with the figure.
• the sequence of edge-collapses and vertex-split operations until only the three outer vertices
• the resulting forest
• perform a selective refinement using a query rectangle
• a stabbing query (or point location)
• a query for contour lines
Question 3: 10 points
You are trying to get a contract from a grocery store chain (such as Loblaws, etc…). Assume
that they have no GIS applications in place. Write a proposal for them to utilize GIS. That means
point out clearly what they could achieve using this technology. What woudl the potential gain
may be and how you would go about achieving this. (software, data, new development,…) Total
about 2-3 page(s).
End of Assignment 2.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com