Please resolve this issue with explanation. 3. onion-peeling depth of a set of p

Question

Please resolve this issue with explanation. 3. onion-peeling depth of a set of points on the 2D plane is defined to be the number of convex huls that can be formed by successively "peeling" the outermost convex hull of the original set is convex hull is computed for the interior points, then removed leaving the "more inter This is done until no points remain. The number of iterations of convex hul peeling depth of the original set of points Determine the onion-peeling depth of the following point set. (10 pts.) hull until no points remain. That is, the computed, then removed leaving the interior points behind. Another ior" points behind. the onion Onion-pe BONUS: What would be the optimal complexity of calulating this v exity value? Defe

Explanation / Answer

Consider a set S of n points on a 2D plane. Compute the convex hull of S, and let S’ be the set of points remaining in the interior of the hull. Then compute the convex hull of S’ and recursively repeat this process until no more points remain.

One ends up with a sequence of nested convex hulls, called the onion-peeling of S.

It works in three phases:-

1. Find an extreme point. This point will be the pivot, is guaranteed to be on the hull and is chosen to be the point with the largest y coordinate.

2. Sort the points in order of increasing angle about the pivot. The resulting polygon is usually a star-shaped polygon in which the pivot can see the whole polygon.

3. Build the hull, by marching around the polygon, adding edges when turning left, and back tracking when turning right.

// Returns the convex hull for the given set of points

vector<pair<int, int>> divide(vector<pair<int, int>> a)

{

    // If the number of points is less than 6 then the

    // function uses the brute algorithm to find the

    // convex hull

    if (a.size() <= 5)

        return bruteHull(a);

    // left contains the left half points

    // right contains the right half points

    vector<pair<int, int>>left, right;

    for (int i=0; i<a.size()/2; i++)

        left.push_back(a[i]);

    for (int i=a.size()/2; i<a.size(); i++)

        right.push_back(a[i]);

    // convex hull for the left and right sets

    vector<pair<int, int>>left_hull = divide(left);

    vector<pair<int, int>>right_hull = divide(right);

    // merging the convex hulls

    return merger(left_hull, right_hull);

}

// Driver code

int main()

{

    vector<pair<int, int> > a;

    a.push_back(make_pair(0, 0));

    a.push_back(make_pair(1, -4));

    a.push_back(make_pair(-1, -5));

    a.push_back(make_pair(-5, -3));

    a.push_back(make_pair(-3, -1));

    a.push_back(make_pair(-1, -3));

    a.push_back(make_pair(-2, -2));

    a.push_back(make_pair(-1, -1));

    a.push_back(make_pair(-2, -1));

    a.push_back(make_pair(-1, 1));

    int n = a.size();

    // sorting the set of points according

    // to the x-coordinate

    sort(a.begin(), a.end());

    vector<pair<int, int> >ans = divide(a);

    cout << "convex hull: ";

    for (auto e:ans)

       cout << e.first << " "

            << e.second << endl;

    return 0;

}

Bonus Answer:- It first explicitly sorts the points in O(n * logn) and then applies a linear-time scanning algorithm to build the hull.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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