Exam Geometric algorithms, February 2014
Time 120 minutes.
1. problem. Consider randomized incremental algorithm which forms a
structure to find the face in a given planar subdivision in which lies given
point. Answer the following questions:
(a) What serves as an input for the algorithm? What is a trapezoidal map?
(2 points)
(b) Describe the searching structure used by the algorithm. Give an example.
(2 points)
(c) Describe the strategy of the algorithm and its main steps. (2 points)
(d) Give a pseudocode of the procedure which finds trapezoids through which
a new added segment goes. (2 points)
(e) How does the searching structure change after a new segment is added?
(2 point)
2. problem. Consider linear programming in the plane. Answer the following
questions:
(a) What is the linear programming in the plane? What is 1-dimensional
linear programming? (2 points)
(b) Which possible outputs (results) does the linear programming in the
plane have? Complete by a picture. (2 points)
(c) What is bounded linear programming in the plane? Describe in details
how it is solved by randomized incremental algorithm. (4 points)
(d) What is the running time for the solution of 1-dimensional linear programming.
What is the running time for the solution of 2-dimensional linear
programming if we do not use the randomized algorithm? What is expected
time when we use the randomized algorithm. (2 points)
3. problem. Answer the following questions:
(a) Define notions of incident face, next edge and previous edge used in the
framework of double connected edge lists. (2 points)
(b) What is the input for Delaunay triangulation? Characterize exactly what
is output of this algoritm. (2 points)
(d) Compare time (for searching) and storage difficulties for 2-dimensional
kd-trees and range trees. (2 points)
(e) Give the pseudocode of the algorithm which desribes what happens when
a sweeping line goes trough a merge point in the algorithm which divides a
polygon into monotone pieces. (2 points)
(e) Describe by a formula that the point r lies on the segment qr. (2 points)
Evaluation
0 – 14 F, 15 – 17 E, 18 – 20 D, 21 – 23 C, 24 – 26 B, 27 – 30 A
1