•   When: Thursday, April 06, 2017 from 12:00 PM to 01:00 PM
•   Speakers: Dr. Dana Richards
•   Location: Nguyen Engineering Room 4201
•   Export to iCal

Given a set P of n points in the plane, the first layer L(1) of P is formed by the points that appear on P's convex hull. In general, a point belongs to layer L(i), if it lies on the convex hull of the set P with points on the first i-1 layers removed. Existing algorithms for this problem either do not achieve the optima O(n log n) runtime and linear space, or are overly complex and difficult to apply in practice. We propose a new algorithm that is both optimal and simple. The simplicity is achieved by independently computing four sets of monotone convex chains which are then merged together.