Problem 1456. Beads on a Necklace (Convex Hulls)

We may describe a convex hull as a rubber band stretched around a list of points. Some of the points will be inside the rubber band, and some will define vertices of (or lie along the edge of) a convex polygon.

Given an n-by-2 list of points xy where each row describes a point, your job is to determine if all the points belong to the convex hull for those points. In the matrix xy, the x coordinate is the first column and the y coordinate is the second column.

So, for example, the points below form a single convex hull.

   *     *
   *     *  

In contrast, the points below do not, since the convex hull is a triangle that includes an interior point. Any polygon that includes all the points must necessarily be concave.

      *
      *  
   *     *

Thus if

 xy = [1 1;1 2;2 2;2 1]

then

 allConvex(xy) => true

Whereas

 xy = [1 1;3 1;2 2;2 3]
 allConvex(xy) => false

Solution Stats

42.75% Correct | 57.25% Incorrect
Last Solution submitted on May 15, 2023

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers47

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!