xyz Interview Question for xyzs
- 0of 0 votes
AnswersA polygon is a piecewise-linear, closed curve in the plane. That is, it is a curve
- jayashriaiyar February 24, 2015 in United States
ending on itself that is formed by a sequence of straight-line segments, called the
sides of the polygon. A point joining two consecutive sides is called a vertex of
the polygon. If the polygon is simple, as we shall generally assume, it does not
cross itself. The set of points in the plane enclosed by a simple polygon forms the
interior of the polygon, the set of points on the polygon itself forms its boundary,
and the set of points surrounding the polygon forms its exterior. A simple polygon
is convex if, given any two points on its boundary or in its interior, all points on
the line segment drawn between them are contained in the polygon’s boundary or
interior.
Professor Amundsen proposes the following method to determine whether a sequence
hp0, p1, . . . , pn−1i of n points forms the consecutive vertices of a convex
polygon. Output “yes” if the set {6 pi pi+1 pi+2 : i = 0, 1, . . . , n − 1}, where sub
script addition is performed modulo n, does not contain both left turns and right
turns; otherwise, output “no.” Show that although this method runs in linear time,
it does not always produce the correct answer. Modify the professor’s method so
that it always produces the correct answer in linear time.| Report Duplicate | Flag | PURGE
xyz xyz Algorithm