A new Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon in the Plane
Oh la la
Your session has expired but don’t worry, your message
has been saved.Please log in and we’ll bring you back
to this page. You’ll just need to click “Send”.
Your evaluation is of great value to our authors and readers. Many thanks for your time.
When you're done, click "publish"
Only blue fields are mandatory.
Your mailing list is currently empty.
It will build up as you send messages
and links to your peers.
besides you has access to this list.
Enter the e-mail addresses of your recipients in the box below. Note: Peer Evaluation will NOT store these email addresses log in
Your message has been sent.
Full text for this article was not available? Send a request to the author(s)
: A new Linear Time Algorithm for Computing the Convex Hull of a Simple Polygon in the Plane
Abstract : The problem of determining the convex hull of a simple polygon has received a lot of attention in the early eighties. The first linear time algorithm for this task proposed by Sklansky in [S72] was based on the simple idea of removing all left turns while moving around the polygon in clockwise orientation. This algorithm was shown to fail in some cases. Since then several correct, yet more complicated linear algorithms have been published and classes of polygons have been determined for which Sklansky's original algorithm can be used. In our note we show how to mend Sklansky's Algorithm in a simple way and prove the correctness of the resulting algorithm. As an application we show how to compute a rectangle of smallest area containing a given simple polygon in linear time. 1 Introduction The problem of determining the convex hull of a simple polygon has received a lot of attention in the early eighties. The first linear time algorithm for this task was proposed by Sklansky in [S72]. S...
Leave a comment
This contribution has not been reviewed yet. review?