Re: Jordan's Curve Theorem for polygons

From: Chan-Ho Suh (suh_at_math.ucdavis.nospam.edu)
Date: 07/11/04 

Date: Sun, 11 Jul 2004 00:39:37 -0700

In article <ccmqoj$jmv$1@panix2.panix.com>, Lee Rudolph
<lrudolph@panix.com> wrote:

> Chan-Ho Suh <suh@math.ucdavis.nospam.edu> writes:
>
> ...
> >There's also a more or less straightforward approach (but somewhat
> >tricky) using induction on the number of sides. The basic idea is to
> >chop up the polygon and then apply the induction hypothesis. This is
> >described by Bing in his book on 3-dimensional topology.
>
> Bing's method has (or can be made to have) the virtue of yielding,
> not just the Jordan Curve Theorem, but the Schoenflies Theorem
> (in a strong form: the union of the polygon and its interior is PL
> ambient isotopic to the union of a triangle-with-lotsa-extra-vertices
> and *its* interior), I believe.
>

You're absolutely correct, Lee. Thanks for pointing this out.

One can show using induction and a simple lemma on "chopping up" a
polygon (this is somewhat misleadingly phrased, see below) that a
polygon on the plane bounds a disc, or a stronger version that says it
is PL isotopic to a triangle using a series of "pushes".

Here's the lemma and its proof:

Lemma: Given a polygon with more than three vertices, there is a
segment connecting two vertices so that the segment only touches the
polygon at its ends.

Remark: Since at this point we can't assume something is either inside
or outside (we haven't shown a polygon separates the plane), we can't
talk about whether such a segment is inside or outside. I think the
phrase "chop up" which I originally used, implicitly assumes this
segment is inside. So it's best to avoid this kind of terminology.

Proof: Pick three consecutive vertices v_1, v_2, v_3. Look at the
segment [v_1, v_3]. If it doesn't touch the polygon in its interior,
we're done. So assume it does. This means the polygon either just
touches [v_1, v_3] in its interior, meaning there is a vertex in its
interior, or there is a vertex contained inside the triangle spanned by
the vertices v_1, v_2, v_3. In the former case, pick such a vertex
and connect it to v_2. This gives the necessary segment. In the
latter case, pick the vertex in the triangle closest to v_2.
Connecting it to v_2 gives the segment. QED.

To prove a polygon bounds a disc, just use the induction hypothesis
that any polygon with number of sides less than or equal to n bounds a
disc. Given a polygon with number of sides n+1, use the lemma to find
a segment that only touches the polygon at vertices x and y. The
polygon together with this segment forms what's called a theta curve:
three simple arcs such that each pair shares the same distinct
endpoints. Call the arcs corresponding to pieces of the original
polygon a_1 and a_2. We can apply the induction hypothesis to a_i
union [x, y] for each i, to get two discs, D_1, D_2. One may be inside
the other, or they may be disjoint except where they meet along [x, y].
The latter case is easily seen to give a disc, since two discs that are
joined along an arc in each boundary gives a disc. In the first case,
say the disc bound by a_2 and [x, y], D_2. is inside the other D_1. We
can push [x, y] keeping its endpoints fixed, across D_2 to a_2. This
is an isotopy of the plane mapping the boundary of D_2 to our polygon,
a_1 union a_2. This shows the polygon bounds a disc.

To prove the stronger version of the Schoenfliess theorem, use the
induction hypothesis that any polygon with number of sides less than or
equal to n can be PL-isotoped by a series of "pushes" to a triangle. A
push here refers to a PL-isotopy of the plane that has compact support,
in particular, you pick a point and look at a star neighborhood of it.
Suppose there's another point in the neighborhood so that the
neighborhood is also a star of it, i.e. the neighborhood is a cone on
two different points p and q. You can realize the map that sends the
cone on p to the cone on q by an isotopy that slides p along a segment
to q. This is a push. I'll refer to a series of pushes also as a
push, for brevity.

The idea here is to find the segment [x,y] and form the theta curve.
Basically here all you have to do is use the fact that two pairs of
arcs in the theta curve bound discs that can be pushed to a triangle
and then argue that the third pair of arcs can also be pushed to a
triangle. As before you'll either have two discs touching along an arc
or one inside the other. In the first case, push one disc into a
triangle. Then you can use the triangle and a push across it to force
everything into the other disc (which probably doesn't look like a
triangle). So by pushes, you've moved the original polygon onto
something that can be pushed into a triangle. The second case I'll
leave to the reader. In this case, instead of sucking everything into
a disc, you have to blow it out onto a disc.

Relevant Pages

  • ANN: FastGEO Computational Geometry Library
    ... * 2D/3D Segment intersection point calculation ... * 2D/3D Triangle, quadix, rectangle, circle and polygon perimeter ... * Closest point on segment from a point ...
    (borland.public.delphi.thirdpartytools.general)
  • Re: Quake performance SGI vs Sun
    ... he said a triangle is a polygon. ... You answered saying that a triangle ... Just the facts. ...
    (comp.sys.sun.hardware)
  • Re: negative z coordinates
    ... I would generate a triangle fan (polygon) rather than a vector of triangles. ... If it's a software rasterizer, ... Then he would clip indexed primitives and write ...
    (comp.graphics.api.opengl)
  • 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)
  • Re: Texture 3D interpolation between layers
    ... this edge has on both endpoints the same texture value in r-component even if it's different height. ... becomes an triangle edge, ogl interpolates itself on this ... but withouth changes with the original polygon. ...
    (comp.graphics.api.opengl)