[Math] Convex hull questions

computational geometrygeometry

Suppose I am in D-dimensional space, e.g. D=2.

  1. What is the minimum number of points to create a valid convex hull? If D = 2, would I need 3 points to create a convex hull (i.e. to form a triangle)? For any D, could I have a convex hull of 1 point?

  2. Suppose I have a convex hull. If I am given a point that lies exactly on the hull, is it considered "inside" / "enclosed by" the hull?

  3. Suppose further that a particular convex hull contains all points labelled "Apple". Now I add another point that is validly inside the hull, but it is "Banana". Is there a way to split the hull into multiple hulls so that the "Banana" point is not in any "Apple" hull?

P.S. I am a software programmer, not a mathematician, so please speak slowly. 🙂

EDIT:
Regarding problem 3, here is an example.

(i) I have a convex hull formed in 2-d space, and all the points are labelled "A".

enter image description here

(ii) Then a point labelled "B" enters the data set. It is within the convex hull, but since it has a different label, I would like to somehow keep the "A" hull pure with only "A" points.

enter image description here

(iii) My first option may be to create a concave hull, which is pure with "A" only.

enter image description here

(iv) My other option, which I suggested in my original question, is to split the big convex hull into two separate convex hulls, each of which is pure with "A" only.

enter image description here

Is this type of problem known in the domain of computational geometry and hulls? I know it's dealt with in machine learning where you create separating "hyperplanes", but here I'm talking purely about hulls and associated nomenclature.

Best Answer

  1. As noted in the comments, a convex hull of one point is just the point by itself, and isn't really a problem. If you want your convex hull to have a nonempty interior, you'd need $D + 1$ points (in general position).
  2. Generally, yes. For convex hulls of points, you'll have points on the boundary (the vertices of the hull, at least), so disallowing the boundary would be a problem. But it is a borderline case :)
  3. Here's one way to do it: Draw any line (or in higher dimension - hyperplane) through the 'banana' point that does not pass through any 'apple' point. Split the apple points into two groups $P_1$ and $P_2$ based on if they lie on one side of the line or the other. Then these two groups have convex hulls that do not include your 'banana'.
Related Question