Re: Example of a set requiring d+1 points (Caratheodory theorem)

Kevin Buhr wrote:

Kevin Buhr <buhr+un@xxxxxxxxxxx> writes:

For an example of a *connected* A where you still need d+1 points, I
don't believe you'll find one in R^1 or R^2, but you'll find it easy
to find one in R^3. Let A be the union of three line segments joined
at a single point (so their convex hull is a tetrahedron). Note that
no interior point can be expressed as a linear combination of only two
points of A.

Oops.. Well, now that I reread what I wrote, that's hardly going to
work, is it? In R^3, you obviously want an example where *four*
points are required.

And, now that I've thought about it, I think in R^d for a connected
set A, you'll never need all d+1 points. You can use connectedness to
"eliminate" a point as follows.

Suppose you have an x in A (subset of R^d)

You mean in the convex hull of A?

expressed as a convex
combination (c.c.) of d+1 points in A: x_0,x_1,...,x_d. If these
points aren't all linearly independent, you can obviously express x as
c.c. of a subset of d or fewer of them, and you're done, so suppose
they *are* independent.

That is a bit of a handwave. Besides, I think you are confusing linear,
affine and convex combinations here. How about this:
If these points are affinely dependent, they are contained in an affine
subspace of dimension d' < d, and Caratheodory's theorem can be used to
show that x is a c.c. of (d'+1) <= d points.
On the other hand, if they are independent, ...

Then, the convex closure of the points is a
d-simplex S(x_0,x_1,x_2,...,x_d). If x is on the boundary, again, you
can immediately express x as a c.c of a subset of d or fewer of the
points, so suppose x is in the interior of the simplex.

Now, as A is connected, there is a path from x_0 to x_1.

Unfortunately, not every connected set is path-connected.

Consider the
"shrinking" d-simplex S(y,x_1,x_2,...,x_d) as y moves along the path
from x_0 to x_1. Geometrically, "x" is contained in the interior of
the original simplex, and as y goes from x_0 to x_1, the simplex
"shrinks". At some point, either at y=x_1 or at some earlier time on
the path, the simplex becomes "flat"---it's no longer a d-simplex.
It's either a (d-1)-simplex or---if this happens before y=x_1 and
depending on the shape of the path---maybe the union of two
(d-1)-simplexes. But sometime between y=x_0 and the first "collapse"
of the simplex, the boundary of the shrinking simplex (or its
collapsed version) must contact x. At that point, x can be expressed
as a c.c. of y and d-1 of the points (x_1,x_2,...,x_d).

Visualizing this in R^2 is easiest: if x is expressed as a c.c. of
three linearly independent points, it's in the interior of the
triangle formed by those three points S(x_0,x_1,x_2). Now, let y go
from x_0 to x_1 along a path in A, and consider the "shrinking"
triangle S(y,x_1,x_2). Eventually, this will collapse to a line
segment, and sometime between the original triangle at y=x_0 and this
collapse x will be on the triangle boundary or the final collapsed
line, expressible as a linear combination of two points y and x_1 (or
maybe y and x_2) in S.

I think that's sound, though I'm sure to be corrected if it's not.
Does that make sense?


I like it, with the restriction that A must be path-connected.
Maybe that restriction can be lifted, but I'm guessing that would require a
completely different proof. Any ideas? Counterexamples?

--
Niels Diepeveen
.

Relevant Pages

  • Re: Example of a set requiring d+1 points (Caratheodory theorem)
    ... You can use connectedness to ... so suppose x is in the interior of the simplex. ... triangle formed by those three points S. ... this will collapse to a line ...
    (sci.math)
  • Re: Crossing between PATCH and plane
    ... If you think about the connectedness that you are envisioning for your points, they are connected in a relatively circular direction. ... unfortunately, to generate an example that would make this procedure fail in general...it is sufficient to create an "ad hoc" convexity where the points along the polygon, for a small piece of the polygon, move in the opposite direction with respect to the positive direction of the angle. ... For each crossing triangle determine the crossing points ...
    (comp.soft-sys.matlab)