Uttar Pradesh Technical University (UPTU) 2007 B.E Computer Science computational geometry - Question Paper
computational geometry
|
*V-1045* Printed Pages : 3 CS 042 | ||||||||||||||||||||||
| ||||||||||||||||||||||
(SEM. VIII) EXAMINATION, 2006-07 COMPUTATIONAL GEOMETRY
Time : 3 Hours] [Total Marks : 100
Note : (1) Attempt all questions.
(2) All questions carry equal marks.
(3) Assume suitable data wherever necessary.
1 Attempt any two parts :
(a) Differentiate between :
(i) Classical and computational geometry
(ii) Plane and 3D line
(iii) Convex and concave in context of computational geometry.
(b) With help of a suitable example explain the impact of model of computation on complexity of a geometric operation.
(c) Discuss, two fields of application of computational geometry highlighting why classical geometry cant be applied in such fields ?
2 Attempt any two parts :
(a) Contrast chain and slab methods for location of a point in a planar subdivision highlighting data structure employed and computational complexity.
AB, BC and AC. Explain how to derive equation of a plane containing this triangle with the information supplied. If the above information is not sufficient, what more information would be required.
(ii) For triangle in part (i) develop an algorithm to indicate if a point P is internal or external. For an external point the algorithm must be able to tell the side with respect to plane containing triangle.
(c) Discuss, in brief, one dimensional range searching problem. Explain how this can be extended to multidimensional range searching.
Attempt any two parts :
(a) (i) Define convex hull. Determine convex hall, if any, for the following figures (you must indicate how you arrived at the solution)
a3
 |
ft? |
a6 &5 Fig. 2
(ii) Discuss in brief two applications of convex hull.
(b) Discuss quick hull technique with help of a suitable example.
(c) Explain Jarviss march for convex hull with help of a suitable example.
Attempt any two parts :
(a) Discuss hidden line problem and an algorithm for the same.
(b) Contrast Divide and conquer approach with 'Locus approach.
(c) Write short notes on :
(i) Voronoi diagram
(ii) Hidden surface problem.
Attempt any two parts :
(a) Discuss significance of rectangle in the field of computational geometry.
(b) Derive an algorithm to determine bounding rectangle of an arbitrary shape. Apply the algorithm to following shape and comment on computational complexity.
Define union and intersection of a set of rectangles. Determine mathematically perimeter of union and intersection of two rectangles. Assume that these rectangles lie in same plane and are not making an angle i.e., aligned as shown below (Figure)
(c)
Rectangle 1
Rectangle 2
V-1045] 3 [ 2085 ]
Fig. 4
|
Attachment: |
| Earning: Approval pending. |
