2. A polygonal path is a sequence of line segments joined end-to-end; the endpoi

Question

2. A polygonal path is a sequence of line segments joined end-to-end; the endpoints of these line segments are called the vertices of the path. The length of the polygonal path is the sum of the lengths of its segments. A polygonal path with vertices (xy)(x2,y2),... ,(xkyk) is monotonically increasing if xx+1 and yy+1 for every index i-informally, each vertex of the path is above and to the right of its predecessor. Figure 2. A monotonically increasing polygonal path with seven vertices through a set of points. Suppose you are given a set S of n points in the plane, represented as two arrays X[1 n] and Y[1 .. n]. Describe and analyze an algorithm to compute the length of the maximum-length monotonically increasing path with vertices in S. Assume you have a sulanun ius: IDENGITx(x, y, x', y') iluaineinnes ilx: l'ugih of ilx: seg.IK3 from (r.y) io You may use the following fact: Given a directed acyclic graph G = (V,E) with lengths on the edges, we can compute the length of the maximum-length directed path in G in O(V E) time. However, your final running time should still be in terms ofn.

Explanation / Answer

Here we will construct a graph

There are n points which will be acting as n nodes

For every node a

For all i points

If x(i) > x(a) and y(i) > y(a) then add an edge from a to i and weight of the edge as distance between point a and point i

Construct the whole graph as described above and the constructed graph will be directed acyclic graph

Maximum number of edges in the graph possible = n*(n-1) = O(n^2)

Now by using the given fact we can find the maximum length in O(V+E) time in directed acyclic graph,

Here E = O(n^2) and V = O(n)

therefore final running time is O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.