CODEWITHSUNDEEP
c++algorithmconvex-hull
Aditya Bahuguna
Aditya Bahuguna

Reputation: 647

Convex hull of all co-linear points?

This is pretty trivial, but still I wanted to know what would be the convex hull if the points are characterized by line x = y i.e. all points are co-linear.Would that be the same case as 2 points i.e. the line segment joining all the points

Upvotes: 0

Views: 1218

Answers (2)

user2566092
user2566092

Reputation: 4661

Traditionally the convex hull of a set of points is computed and outputted as the convex hull of the vertices (since this is the same as the convex hull of the original set of points, but it is a smaller and non-redundant description). So, traditionally to compute a convex hull, you compute the vertices of the convex hull and then say you are done. If all your points lie on a line, then there are only two vertices: The two extreme endpoints along the line. Thus traditionally you would represent the convex hull by saying that it is the convex hull of these two extreme points (the two vertices), which is the line segment connecting the two vertices by definition of convex hull.

Upvotes: 3

Juan Lopes
Juan Lopes

Reputation: 10565

From wikipedia, Convex Hull is the "smallest convex set that contains X". If that convex set is a polygon, it may be represented by the points in its vertices. But it isn't the points.

So, what should you output depends on how the problem requests you to represent the convex hull. Usually you will only have to output the two farthest points, but some problems may accept colinear points in the answer.

As an exercise, think that the convex hull may not be a polygon:

convex hull

Upvotes: 1

Related Questions