CGAL users discussion list

Le Mer 7 mars 2007 4:06, Iosif Pinelis a écrit :
> This may contain some good ideas, but I have some comments here:
>
>     * first of all, there should essentially be two parts of proof: (1)
>       that your definition of convexity implies that the CGAL test says
>       "yes" and (2) vice versa. It seems that you present a sketch of
>       proof of (2) only. (Am I right?)

No. I show that in the flat and non-flat case, CGAL gives the right answer.

>       But implication (1) does not seem
>       trivial. Even the terms of your definition (a mix of topology,
>       algebra, and order) are quite different from the terms of the CGAL
>       test (no topology, and quite different kinds of algebra and
>       order).  I think that quite a bit of translation from the one
>       language into the other is needed here.

The topological definition I gave is just there to express the condition
for flat polygons in terms of topological closure instead of an ad hoc
condition. I leave it to you to check that the two definitions are
equivalent (the topological one, and the one with the number of edges a
non-vertex should belong to).

>     * Moreover, in your proof of implication (2)(?), you just say: "If
>       it has no self intersection, it is convex". This is obviously not
>       true in general, even if "three successive vertices are never
>       aligned".

You forget that we are in the locally convex case. This is completely
true. If it were non convex, you would have a ray starting inside its core
and intersecting it twice or more. By winding around the origin of the ray
and assuming simplicity, you would obtain that the polygon is
disconnected. Hence it is convex.

> Overall, sorry, I do not believe that this constitutes a proof.

Ok. I think everything is said in the sketch of proof I wrote. I leave you
the details to fill.
-- 
Camille Wormser