Explanation In computational geometry, the convex hull is the line that is enclosed and contains a set of points in a plane so there are no curves in the line or we can say that it is a smallest polygon which encloses a set of points such that every point in the set lies within that polygon. There are many algorithms to find the convex hull of a set of points in the plane. Three algorithms that are most used are graham scan algorithm, Jarvis algorithm and divide-and-conquer algorithm. In graham scan algorithm, there are n numbers of points in any set and if its size of geometric problem increases then it achieves the optimal asymptotic efficiency of O ( n log n ) time. In this algorithm we start by finding the point with lowest y -coordinate, if y -coordinate exists in more than one point in the set then we will choose the point with lowest x -coordinate and call it point p . Next we will sort the remaining points in increasing order according to the angle that are making between these points and point p , now call it point X and add it to the convex hull. After this we will check the last three points if they are making the right turn or left turn, if they make right turn then the second last point does not exist inside it and we will remove that point from convex hull. We will repeat this step until we comprise a left turn, if at any stage three points are in same line we will remove one line or we can keep it, it depends on the requirement. This is the Graham scan algorithm. Next is Jarvis algorithm, Jarvis algorithm is one of the simplest algorithm for finding the convex hull of a set of points in the plane

8th Edition

ISBN: 9781307447118

Author: ROSEN

Publisher: MCG

See similar textbooks

Concept explainers

Set Theory

Every field in the present world involves a set. The theory of sets was developed by German mathematician Georg Cantor while working on the “problems of trigonometric series”.

Question

Chapter 8, Problem 11WP

To determine

To define:

The convex hull of a set of points in the plane and describe three different algorithms including a divide-and-conquer algorithm for finding the convex hull of a set of points in the plane.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 8, Problem 10WP

Chapter 8, Problem 12WP

Students have asked these similar questions

Let W be a window with corners (0,0),(8,0),(8,4) and (0,4). Clip a triangle withvertices (1,1),(10,2) and (5,9) against the window W by tracing Liang Barskeyline clipping algorithm.

determine the number of vertices and edgesand find the in-degree and out-degree of each vertex for thegiven directed multigraph.

5. Can somcone cross all the bridges shown in this map cxactly once and return to the starting point?

Chapter 8 Solutions

DISCRETE MATH.+ITS APPLICATIONS CUSTOM

Ch. 8.1 - Use mathematical induction to verify the formula...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - A vending machine dispensing books of stamps...Ch. 8.1 - A country uses as currency coins with values of 1...Ch. 8.1 - How many was are there to pay a bill of 17 pesos...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...Ch. 8.1 - a) Find a recurrence relation for the number of...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

The convex hull of a set of points in the plane and describe three different algorithms including a divide-and-conquer algorithm for finding the convex hull of a set of points in the plane.

Solution Summary: The author describes three algorithms for finding the convex hull of a set of points in the plane: graham scan, Jarvis, and divide-and-conquer.

Concept explainers

To define: The convex hull of a set of points in the plane and describe three different algorithms including a divide-and-conquer algorithm for finding the convex hull of a set of points in the plane.

Want to see the full answer?

Chapter 8 Solutions

To define:

The convex hull of a set of points in the plane and describe three different algorithms including a divide-and-conquer algorithm for finding the convex hull of a set of points in the plane.