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

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

--
Kevin Buhr <buhr+un@xxxxxxxxxxx>
.

Relevant Pages

  • Re: Example of a set requiring d+1 points (Caratheodory theorem)
    ... You can use connectedness to ... Besides, I think you are confusing linear, ... so suppose x is in the interior of the simplex. ... triangle formed by those three points S. ...
    (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)