CGAL users discussion list

[Iosif Pinelis <>]

 wrote:

> Le Mer 7 mars 2007 1:06, 
>
>  a écrit :
>  
>
> > - in the case of non flat polygons, we can assume that three successive
> > vertices are never aligned (by removing unnecessary vertices), and we have
> > a non-flat locally convex curve P. If it has no self intersection, it is
> > convex, and it has exactly 2 changes of lexicographic order. If it has
> > self intersections, we have to show that there are at least 3 changes of
> > lexicographic order. Let us call X some intersection point. We can split P
> > at X into two polygons, P1 and P2. As any polygon, P1 and P2 have at least
> > 2 changes of order each. P is the union of P1 and P2. As such, it has at
> > least 2 + 2 changes, maybe minus one, in case X is a point with an order
> > change for both P1 and P2. Hence, we always have at least 3 changes in
> > case there is an auto intersection. This concludes the proof.
> >    
>
> Sorry, slight mistake: "maybe minus one, in case X is a point with an
> order change for both P1 and P2" should be replaced by "maybe minus one,
> in case X is a point with an order change for P1 or for P2".
>  
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?) 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.
   * 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". Perhaps you wanted instead to say here something like
     this: "If all the determinants are positive (say) and the polygon
     has no self intersection, then it is convex -- that is, then "the
     union of its bounded side and its edges is [a] convex [set]". But
     such a claim does not seem trivial either. Again, even the
     disparity in the terms here is still great.
   * In addition, I'd guess that in the CGAL programming code a polygon
     is given just as a sequence of points, rather than a closed
     piecewise linear curve (that is, a certain equivalence class of
     periodic piecewise linear maps of R into R^2) as in your
     definition. So, the proof will require a bit more translation
     because of this additional discrepancy. But this seems to be a
     comparatively very minor point.

Overall, sorry, I do not believe that this constitutes a proof. By now 
pretty extensive experience with my own and other papers, reflected in 
part at http://arxiv.org/abs/cs.CG/0609141 and 
http://arxiv.org/abs/cs.CG/0701045 , tells me that careful proofs 
concerning polygon convexity are not that easy, and they are highly 
susceptible to errors (originating from "obvious" pictures).

Iosif Pinelis

P.S. Thanks a lot for sending me the files and corresponding 
suggestions. I'll try to make use of them. I hope I wouldn't have to 
also read other files than these two, but am afraid this won't be the 
case. :-)