search - Convex hull with constant size or triangular form -

i know quickhull algorithm runs in theta(n), if convex hull triangular or has constant size.

what's means?

i'm not sure shape (if looks triangle), because algorithm uses 4 extreme points.

thanks

if number of vertices of convex hull, let h, constant (doesn't depend on n), quickhull takes time proportional n (more precisely c1.n < t < c2.n 2 constants c1 , c2).

when h=3, hull triangle. regardless way algorithm works, has return triangle. careful implementations should work h=2 (a line segment) or h=1 (a single point).