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.

Improve this question
$\endgroup$
3
  • 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, 2014 at 23:30
  • $\begingroup$ @Kaya, I don't get what you mean :(, isn't the presented polygon not convex? $\endgroup$
    – IssamLaradji
    Mar 29, 2014 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, 2014 at 0:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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