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.

  • $\begingroup$ 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? $\endgroup$
    – Ian Coley
    Sep 17, 2013 at 20:18
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 17, 2013 at 20:26

1 Answer 1

  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'.
  • $\begingroup$ Thanks. Can you point me to any resources on how to create a line or hyperplane through the "B" point that does not pass through any "A" point? $\endgroup$ Sep 18, 2013 at 7:48
  • $\begingroup$ In practice, because there are only finitely many points and so many choices for hyperplanes, any randomly chosen hyperplane should work. $\endgroup$ Sep 18, 2013 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.