# Convex hull questions

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". (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. (iii) My first option may be to create a concave hull, which is pure with "A" only. (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. 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.

• In general you need only $n+1$ points in $n$-dimensional space to create a convex hull, e.g. a triangle in the plane, a tetrahedron in space. These simplest hulls can be called simplices (en.wikipedia.org/wiki/Simplex). I believe these hulls are closed, so they contain their boundaries. As for your last question, could you give a little more information about what you mean? – Ian Coley Sep 17 '13 at 20:18
• One can talk about the convex hull of any set of points, no matter how small or large. But you do need $n+1$ points to have a convex hull in $\mathbb{R}^n$ with nonempty interior. – Harald Hanche-Olsen Sep 17 '13 at 20:26

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).
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'.