Asked by Ivan Abraham
on 13 Jun 2016

Here are the definitions I am dealing with.

- In all cases the convex hull of a point is the point itself and the convex hull of coincident points are the points themselves.
- In 1-D space, the convex hull of a two points is the line segment joining the two points.
- In 2-D space, the convex hull of (a) two points is the line segment joining them and that of(b) three or more points is (i) the line segment joining the two extremal points if they are collinear or (ii) the usual definition.
- In 3-D space, the convex hull of (a) two points is the line segment joining them in 3-D space, (b) three points is (i) the line segment joining the two extremal points if they are collinear, or (ii) the triangle formed by them in the plane defined by the three points. Similarly the convex hull of (c) four or more points is (i) the line segment joining the two extremal points if they are all collinear, or (ii) the quadrilateral formed by them if they all line in the same plane or (iii) the usual definition of a tetrahedral
- and so on.

My problem is that convexhulln doesn't handle the degenerate cases. It always needs (n+1) non-collinear points in an n-dimensional space to run. Is there a fix for this; or a way out of this? My overall aim is to check if some given test point is in the convex hull of a given set of points (where the degenerate definitions of convex hull hold as defined above).

Example:

p1=[0 0 0];

p2=[0 0 4];

p3=[-5 0 4];

P=[p1;p2;p3];

Then the convex hull of P is triangle in the x-z plane (that is y=0 plane) with vertices at [-5,4], [0,4] and [0,0] and I want to check some point (obviously with y-coordinate 0) belongs to this triangle.

Thank you for your help in advance.

Answer by John D'Errico
on 13 Jun 2016

Accepted Answer

You can want convhulln to work as you wish, but wishing won't make it so. Code does as it is designed to do. In this case, it is clear that convhulln is not designed to work with degenerate cases. That is a choice made which is entirely valid.

Anyway, I'm not really sure that I agree with all of your "definitions".

For example, to call a line segment the convex hull of two points in a 1-d space seems wrong. In general a convex hull will be an object of manifold dimension one less than the set representing the volume described. So the convex hull of a triangle in 2-dimensions will be composed of line segments. We might call it a 1-manifold.

So in one dimension, the convex hull of two points will at most be a 0-manifold, composed of the endpoints of the included line segment.

As far as the convex hull of a triangle in 3-dimensions goes, it is apparently a decision made by TMW to fail. For example:

>> convhulln(rand(2,3))

Error using cgprechecks (line 40)

Not enough unique points specified.

Error in convhulln (line 41)

cgprechecks(x, nargin, cg_opt);

In fact, I completely agree with that decision. The presumption is that the convex hull of a list of points in n dimensions will be an (n-1)-manifold. If that must fail to be true, then the code will return an error.

So the convex hull of two points in R^3 will also fail, for the same reason. Such a convex hull would be computationally useless, even were you able to define it as a convex hull. Testing if a point lies "inside" that convex hull would virtually always fail due to floating point arithmetic. To know that a point lies EXACTLY on any given line is difficult. So to know that a point lies inside a such a degenerate convex hull will be a test of tolerance.

Similarly, this will fail:

convhulln([1 1;2 2;3 3])

It generates a rather messy looking message. The convex hull is degenerate. Yes, you can fix that using a joggle, convincing the convex hull to think the set is non-degenerate. Still, any test for inside that set will be problematic.

Are there things you can do? Yes, of course. You can put a wrapper around convhulln for your own usage, that tests for degeneracy in these forms and deals with any degeneracies as you desire. That is a virtue of MATLAB. You can always make it do as you like. Of course, testing for a point "inside" a degenerate convex hull can be nasty. You will want to work with projections into a lower dimensional subspace, working with (user supplied) tolerances on the result.

Ivan Abraham
on 13 Jun 2016

Thanks John for that. I know MATLAB functions are designed to cater to the most useful and common applications. I am not much of a computational person, but from a purely mathematical/geometric standpoint there is nothing wrong with defining the convex hull of two points in 1D as the line segment joining them. Given p1 and p2, I can write any point p in the line segment as p=L*p1+(1-L)*p2 where L is in [0,1]. Example take p1=3, p2=10. Then any point in [3,10] can be written as above. Moreover there is nothing wrong with extending this notion to higher spaces; for example 2-D or 3-D, the same concept holds. When you have more than two points you require the coefficients (because there will be more than 2 now) to be non-negative and to sum to one. That is all.

I understand your answer but I am just wondering if there was someone who attempted what I am doing; and how they got around it. I am willing to work with wrappers; but can you expound on what you mean by projections into lower dimensional subspaces (and how to do that in MATLAB)? A good reference or nice example will be very helpful and I can try to work off that. Thanks again!

John D'Errico
on 13 Jun 2016

You can define it anyway you want. What I said is that your definition is not consistent! A convex hull is a lower dimensional object than that which it contains. Think of it as a boundary set.

So it if you have two points, they define a line segment, in any number of dimensions they happen to live in. It is still a line segment, a 1-dimensional thing. To define the convex hull of those two points, to be consistent, the convex hull must be a zero-dimensional object, composed of the two endpoints of the line. It CONTAINS (is the boundary of) the line segment between them. But it is NOT the line segment itself. So I'll argue there IS something wrong with the definition you have chosen.

You can make any definitions you wish of course. But if you choose definitions that are not consistent, then expect problems somewhere along the way. Mathematics can be that way.

You can use the singular value decomposition to test for the effective dimensionality of a set of points, as well as generate projections into a subspace that contains the points. Somewhat less computationally intensive, you can also use a pivoted QR to do the same. (Of course, you might argue that the SVD is a better tool for the purpose, though more computationally expensive. I used qr because I had fairly heavy use planned for this tool.)

I've attached rowspaces to this comment. It is a tool that can be used to test the dimensionality of a set of points. Note that if you will use this tool, you need to subtract off one of the points from the remainder. (Else expect garbage.) You could also subtract off the mean, for example. Any point that can be written as a linear combination of the points in your set will suffice.

A = [1 2;2 3;3 4];

A1 = A(1,:);

Ahat = bsxfun(@minus,A,A1)

Ahat =

0 0

1 1

2 2

[rowbasis,nullspace,dimsfound] = rowspaces(Ahat)

rowbasis =

-0.70711 -0.70711

nullspace =

-0.70711 0.70711

dimsfound =

1

Clearly, the rows of A represent a line in the (x,y) plane. 3 collinear points, in two dimensions. That is reflected in the third returned argument of rowspaces.

Projected into the lower dimensional subspace of the line those points live in, we see this:

Aproj = Ahat*rowbasis'

Aproj =

0

-1.4142

-2.8284

And we can recover the original set as:

bsxfun(@plus,Aproj*rowbasis,A1)

ans =

1 2

2 3

3 4

As far as a reference, it is just basic applied linear algebra. Lots of texts out there.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.