Question

Problem 1 (5+15 points)

Consider the set P of n points and suppose we are given the points of P one point at a time. After receiving each point, we compute the convex hull of the points seen so far.

1. (a) As a naive approach, we could run Graham’s scan once for each point, with a total running time of O(n2 log n). Write down the pesuedocode for this algorithm.

2. (b) Develop an O(n2) algorithm to solve the problem. Write down the pseudocode and analyze the running time of your algorithm.

Answer 1

solution:

Given data:

a)

#include <iostream>

#include <stack>

#include <stdlib.h>

using namespace std;

struct point

{

int , l;

};

point p0;

// A utility function to find next to top in a stack

Point nextToTop(stack<Point> &S)

{

    Point p = S.top();

    S.pop();

    Point res = S.top();

    S.push(p);

    return res;

}

// A utility function to swap two points

int swap(Point &p1, Point &p2)

{

    Point temp = p1;

    p1 = p2;

    p2 = temp;

}

// A utility function to return square of distance

// between p1 and p2

int distSquare(Point p1, Point p2)

{

    return (p1.k - p2.k)*(p1.k - p2.k) +

          (p1.l - p2.l)*(p1.l - p2.l);

}

int orientation(Point p, Point q, Point r)

{

    int value = (q.l - p.l) * (r.k - q.k) -

              (q.k - p.k) * (r.l - q.l);

    if (value == 0) return 0; // colinear

    return (value > 0)? 1: 2; // clock or counterclock wise

}

int compare(const void *vp1, const void *vp2)

{

   Point *p1 = (Point *)vp1;

   Point *p2 = (Point *)vp2;

   // Find orientation

   int o = orientation(p0, *p1, *p2);

   if (o == 0)

     return (distSquare(p0, *p2) >= distSquare(p0, *p1))? -1 : 1;

   return (o == 2)? -1: 1;

}

void convexHull(Point points[], int n)

{

   // Find the bottommost point

   int ymin = points[0].y, min = 0;

   for (int i = 1; i < n; i++)

   {

     int y = points[i].y;

     // Pick the bottom-most or chose the left

     // most point in case of tie

     if ((y < ymin) || (ymin == y &&

         points[i].x < points[min].x))

        ymin = points[i].y, min = i;

   }

   // Place the bottom-most point at first position

   swap(points[0], points[min]);

   // Sort n-1 points with respect to the first point.

   // A point p1 comes before p2 in sorted output if p2

   // has larger polar angle (in counterclockwise

   // direction) than p1

   p0 = points[0];

   qsort(&points[1], n-1, sizeof(Point), compare);

   // If two or more points make same angle with p0,

   // THEN,Remove all but the one that is farthest from p0

   // Remember that, in above sorting, our criteria was

   // to keep the farthest point at the end when more than

   // one points have same angle.

   int m = 1; // Initialize size of modified array

   for (int i=1; i<n; i++)

   {

       // Keep removing i while angle of i and i+1 is same

       // with respect to p0

       while (i < n-1 && orientation(p0, points[i],

                                    points[i+1]) == 0)

          i++;

       points[m] = points[i];

       m++; // Updates size of modified array

   }

   if (m < 3) return;

   stack<Point> S;

   S.push(points[0]);

   S.push(points[1]);

   S.push(points[2]);

   // Process remaining n-3 points

   for (int i = 3; i < m; i++)

   {

      while (orientation(nextToTop(S), S.top(), points[i]) != 2)

         S.pop();

      S.push(points[i]);

   }

   // Now stack has the output points and hence print contents of stack

   while (!S.empty())

   {

       Point p = S.top();

       cout << "(" << p.k << ", " << p.l<<")" << endl;

       S.pop();

   }

}

// Driver program to test above functions

int main()

{

    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},

                      {0, 0}, {1, 2}, {3, 1}, {3, 3}};

    int n = sizeof(points)/sizeof(points[0]);

    convexHull(points, n);

    return 0;

}

b)

#include <bits/stdc++.h>

using namespace std;

struct Point

{

    int x, y;

};

int orientation(Point p, Point q, Point r)

{

    int v = (q.y - p.y) * (r.x - q.x) -

              (q.x - p.x) * (r.y - q.y);

    if (v == 0) return 0; // colinear

    return (v > 0)? 1: 2; // clock or counterclock wise

}

// Prints convex hull of a set of n points.

void convex_Hull(Point points[], int n)

{

    // There must be at least 3 points

    if (n < 3) return;

    // Initialize Result

    vector<Point> hull;

    // Find the leftmost point

    int l = 0;

    for (int i = 1; i < n; i++)

        if (points[i].x < points[l].x)

            l = i;

    // Start from leftmost point and keep moving counterclockwise

    // until we reach the start point again, This loop runs O(h)

    // times where h is number of points in result.

    int p = l, q;

    do

{

hull.push_back(points[p]);

        q = (p+1)%n;

        for (int i = 0; i < n; i++)

        {

           if (orientation(points[p], points[i], points[q]) == 2)

               q = i;

        }

        // Now q is the most counterclockwise with respect to p

        // Set p as q for next iteration, so that q is added to

        // result 'hull'

        p = q;

    } while (p != l); // While we don't come to first point

    // Print Result

    for (int i = 0; i < hull.size(); i++)

        cout << "(" << hull[i].x << ", "

              << hull[i].y << ")\n";

}

int main()

{

    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},

                      {3, 0}, {0, 0}, {3, 3}};

    int n = sizeof(points)/sizeof(points[0]);

    convex_Hull(points, n);

    return 0;

}

please give me thumb up