Algorithm
Development Kit 1.0

Package algs.model.problems.convexhull.andrew

Defines solution to the Convex Hull problem proposed by Andrew, which is a ConvexHullScan.

See:
          Description

Class Summary
ConvexHullScan Computes Convex Hull following Andrew's Algorithm.
ConvexHullScanLinkedList Computes Convex Hull following Andrew's Algorithm with linked lists.
PartialLinkedListHull Represents either the top or the bottom of a Convex Hull.
 

Package algs.model.problems.convexhull.andrew Description

Defines solution to the Convex Hull problem proposed by Andrew, which is a ConvexHullScan. Andrew's ConvexHullScan devises a novel approach towards computing the partial upper hull for a set of points by first sorting all points by their x coordinate (breaking ties by considering the y coordinate). The partial upper hull starts with the leftmost two points in P. ConvexHullScan extends the partial upper hull by finding the point in P whose x coordinate comes next in sorted order after the partial upper hull's last point Li. Once computed, the lower partial hull is similar computed (this time by processing points from right to left). The two partial hulls are merged to produce the final hull.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.