CGAL users discussion list

[Iosif Pinelis <>]

 wrote:

> 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.
Come on Camille. Your own example, from your latest post, shows that 
CGAL does not give the right answer. You can say that was a minor bug. 
So, let us get back to your proof. How does one prove that something is 
_not_ a proof? That may sometimes be more difficult to prove than the 
thing itself!

I asked if you presented only a sketch of proof of implication (2) (but 
not of implication (1)). You answer "No." But I can't find anything 
concerning (1) in your proof, even though I have tried pretty hard.

Indeed, let us discard (just for the simplicity/brevity sake) the flat 
case (which is trivial anyway) and focus on the non-flat case. Let us 
consider in detail all that you wrote for that case:

> - in the case of non flat polygons, we can assume that three successive
> vertices are never aligned (by removing unnecessary vertices), 

Well, even at this comparatively minor point, some care should exercised, 
depending especially on how exactly the test deals with such degeneracies (we 
discussed this a bit back and forth).


> and we have
> a non-flat locally convex curve P. 

Here you are assuming the local convexity, which you said is part of the CGAL test. So, this assumption seems to pertain to implication (2), that the CGAL test's "yes" implies the polygon convexity. 

> If it has no self intersection, it is
> convex, and it has exactly 2 changes of lexicographic order. 

The conclusion here, that P is convex, again seems to pertain to the same 
implication (2). (Even though no immediate reasons for this conclusion are 
given.)

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

In this part of the proof, you apparently try to show that lack of simplicity implies 
that the CGAL test says "no" (for the reason of more than 2 changes of 
order). Equivalently, this would mean that the only-two-changes condition of the test 
implies the simplicity, which is one (but not all) of the polygon convexity conditions 
required by your definition. So, this last quote is seen as an attempt to prove the 
same implication (2). Another way to look at this is that here you try to show that the 
only-two-changes condition of the test implies the simplicity, in which case you have 
already addressed implication (2) in some way. However, here again your reasoning is 
far from sufficient. Indeed, just for one thing, here you are not in any way using the 
condition of the CGAL test that all the determinants be of the same sign; nor are you 
even referring to that condition, without which your counting of the order changes is 
in general incorrect. Consider e.g. polygon Q with vertex list 
((0,0),(1,1),(1,0),(0,1)); then Q is self-intersecting and thus not simple (and also 
not convex), but it has only 2 changes of lexicographic order.

> This concludes the proof.

Well, we can summarize now. 

  1. Your own example contradicts your proof.
  2. The implication (1) of your claim is nowhere addressed in the proof.
  3. The proof of the other half of the claim (implication (2)) is
     essentially insufficient on several counts.

It remains to address just a few details.

> >      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).
This particular topological aspect of your definition of polygon 
convexity is indeed comparatively simple, and it is not what I meant. 
Rather, if you spell out the term "bounded side" in your defintion:

> non-simple polygons are not convex, a simple polygon is convex if the
> union of its bounded side and its edges is convex

then you'll get this: "the bounded connected component of the complement of the image of the polygon in R^2", and it is connectedness that is the nontrivial and essential topological aspect. However, it was never used (or even referred to) in your proof. 

> >    * 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. 
No, I don't forget. But, again, you never even referred to local 
convexity in your original proof. Nor did you ever say which way you are 
proving: (1) or (2).

> This is completely
> true. If it were non convex, you would have a ray starting inside its core
> and intersecting it twice or more. 
In other words, you are saying that, if a polygon P is simple and all 
the determinants are positive and all rays originating in the bounded 
connected component IP of the complement of P intersect P (at most) 
once, then the union of P and IP is a convex set. This statement looks 
far from obvious. Exactly why is do you say it is true?

> By winding around the origin of the ray
> and assuming simplicity, you would obtain that the polygon is
> disconnected. 
Again, exactly how would I obtain this?

> 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.
>  
Thanks for giving me this job. :-)  I may take it at some point. 
However, so far I frankly do not see how to utilize any of your 
suggestions. Rather, I think the CGAL polygon convexity test is pretty 
similar to the LEDA test, whose proof can be found at 
http://arxiv.org/abs/cs.CG/0701045 .  So, I believe the CGAL test can be 
proved similarly to the LEDA test and/or using the latter test.

That you leave the job to me seems rather strange, though. Let me remind 
you that my questions were as follows:

  1. What is the definition of polygon convexity assumed in CGAL?
  2. What is the CGAL polygon convexity text?
  3. Is there a complete, rigorous proof that the test exactly
     corresponds to the definition?

It seems that you (apparently as a person speaking for the CGAL team, 
no?) gave me more or less clear answers to Questions 1 and 2; however, 
you had to change the versions a couple of times.

Concerning Question 3, the most important one, you presented what you 
said was a sketch of proof, but, for the reasons explained above, I 
regret to say that I do not believe that it qualifies even as a sketch.

However, I am pleased to hear that, at least, this discussion has helped 
to find a bug in the code. In my view, this and several other aspects of 
this discussion confirm that careful proofs (and even definitions) 
concerning polygon convexity are not that easy, and they are highly 
susceptible to errors (originating from "obvious" pictures).  Therefore, 
I hope that a standard, generally accepted definition of the polygon 
convexity and careful, detailed proofs will be more widely recognized 
and appreciated.

--
Iosif Pinelis, Professor
Department of Mathematical Sciences
Michigan Technological University
Houghton, Michigan 49931-1295 USA