0
$\begingroup$

Context

Consider this algorithm. If the set $\{\angle p_ip_{i+1}p_{i+2} : i=0,...,n-1\}$ does not contain left and right turns, output "yes the polygon is convex"; otherwise, "no".

My answer

Consider this nonsimple polygon having 4 vertices; the algorithm above will output "yes" as the set of points does not contain both left and right turns, yet the polygon is not convex. Is this a good counterexample rendering the above algorithm incorrect?

enter image description here

Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ Your answer does not seem like a valid counterexample. You present a face for which the algorithm will return 'yes, it is convex' and then assert that the shape is not convex--a fact which is not clear upon inspection. $\endgroup$ – Kaya Mar 28 '14 at 23:30
  • $\begingroup$ @Kaya, I don't get what you mean :(, isn't the presented polygon not convex? $\endgroup$ – Curious Mar 29 '14 at 0:08
  • 2
    $\begingroup$ The face in the interior seems to be a a quadrilateral with straight sides. The only way I know of for one of these to be non-convex is if there is some interior angle greater than $\pi$ radians. The one you present seems like each of the four interior angles is approximately $\pi/2$. $\endgroup$ – Kaya Mar 29 '14 at 0:13
3
$\begingroup$

A simple counterexample is a pentagram (http://en.wikipedia.org/wiki/Pentagram). It contains right turns (if you go in clockwise direction) only, but it is not convex. The above algorithm will incorrectly say pentagram is a convex polygon. It's actually a complex polygon.

In other words, algorithm might fail if the input polygon is complex.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.