Geometric algorithms Flashcards
Describe algorithm for two closest pair of points in R2 (divide and conquer)
Similar to quicksort - we chose a median m, then set P1 contains elements that are less than or equal to m, set P2 that are greater then m. Then we recursively call this function onto P1, P2.
Define runtime of closest pair of points in R2(divide and conquer)
O(nlogn)
Write a recurrence to closest pair of points in R2 (divide and conquer)
T(n) = 2*T(n/2) + O(n)
Write two assumptions needed to perform a sweep-line technique
- no segments are vertical
- no three segments intersect in the same point
Describe what means that two segment lines are comparable w.r.t. sweep line
If they both intersect L (sweep line) but not in the potential intersection of s1, s2. We define s1 < s2 if s1 lies below s2 on L
Define runtime of sweep-line algorithm
O(nlogn)
How much space we need to store a connected planar graph?
O(n + m + f), but recalling Euler’s theorem gives us: m <= 3n-6 and f<=2n-4, so we need just O(n) space.
How do you construct Voronoi diagram?
Let p be a point in a plane. Connect p to its closest neighbour p’ - let s be the line segment. Construct a paralel line to s such that distance between p and the line is equal to the distance of p’ and the line. We will do this till we get a Voronoi cell around the point p
In which time can Voronoi diagram P of n points be computed?
O(nlogn)
What is Delaunay-graph DG(P) ?
It is just a straight-line drawing of G
How fast can we compute a Delaunay-graph if we have Vor(P)?
O(n)
For what can be Delaunay triangulation used?
Finding the closest pair of points in O(nlogn) time
