1-Shortest path below. Let a set of points S and two additional points a and b b
ID: 3911628 • Letter: 1
Question
1-Shortest path below. Let a set of points S and two additional points a and b be given, with left of S and b right of S. Develop an algorithm to find the shortest path from a to b that avoids the interior of S. Assume a convex hull algorithm is available.
2-Average time complexity of QuickHull (Scot Drysdale). Argue that QuickHull's average time complexity on points uniformly distributed within a square is o(n). Hint: The area of a triangle is half the area of a surrounding parallelogram with the same base.
Explanation / Answer
Answer 1:The problem statement can be restated as finding the shortest path between the soure and destination points without touching ie avoiding a set of points.
First of all prepare a visibility graph for the points and obstacles in euclidian plane.Each node would be a location point and edges would be any visible connection between the nodes.When convex hull on each of the polygon on the visibility map are determined then find convex hull for each polygon in the plane.Create a medium for shortest path algorithm to run. The visibility graph shall contain all all possible routes betwen start and end points and can be used with shortest path algorithm like Dkjistra to find the optimal shortest path.The weight for the vertices are the distances between them.
Answer 2: Consider a set of points [0....n-1]. In order to find the coplex hull of these points (cartesian points) we apply the following quick hull algorithm.Te process is similar to quicksort.
a. Find the point with minimum X coordinate value and max X coordinate values . Let them be X -min and X-max respectively.
b. join these points by a straight line say K. Now the straight line divides the spatial plane of points into two parts
c. For one of the part select the point say P which is at maxmum distance from the line K. For the triangle with points X-max ,X-min and P the points residing inside the triangle is not part of convex hull
d. The lines joining P and X min and P and X-max are the new lines and the process is repeated recursively and only the poits residing outside the triangle are the set of points . Step C is repeated till no points are left out with line. We then add the end points of these ponts to form the quick hull.
It can be summarized as :
QuickHull (Q, l, r)
if Q={ } then return ()
else if Q={l, e} then return (l, e) // unitary quick hall edge
else
T = index of a point that is furthest (max distance) from xy.
Let M be the set containing points strictly right of (x, z)
Let N be the set containing points strictly right of (z, y)
return {QuickHull (M, x, z) U (z) U QuickHull (N, z, y)}
Each of the partitions are determined by the line joining the distinct extreme points leftmost point (1) and extrememe rightmost point(e.).
The time complexity of finding the extreme points is O(n). The analysis is similar to quicksort.The time execution is directly proportion to the input size. When the points are distrbuted within a square each of the partition is uniform.For each recursion the problem will be reduced to a fraction of the original problem size.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.