Finding the convex hull of line intersections in O(n log n) time

The convex hull of line intersections can be found in O(n log n) time by:

• Sorting the lines in descending order by slope
• Finding the set of intersection points of consecutive lines in the ordering (including the last and first line)
• Computing the convex hull of these points using an O(n log n) algorithm such as Graham Scan

Dr. Mikhail Atallah's 1986 description and proof of the algorithm can be found here.

Demo Applet

The demo applet allows you to step though the algorithm using the Graham Scan to compute the convex hull. The applet ensures that all of the line intersections occur within the applet view.

• # of lines -- the number of lines to create
• Random -- create a random set of lines
• Reset -- start the algorithm over on the current set of lines
• Step -- goto the next step in the algorithm