Cache-Oblivious Output-Sensitive Two-Dimensional Convex Hull
Peyman Afshani, Arash Farzan · Canadian Conference on Computational Geometry · 2007
We consider the problem of two-dimensional outputsensitive convex hull in the cache-oblivious model. That is, we are interested in minimizing the number of cache faults caused when computing the convex hull of a set of N points on a plane. We are interested in the outputsensitive case where number of cache misses are analyzed in the worst case based on both the input size N and output size H (number of extreme points that lie on the flnal convex hull ). There is the lower bound of N B log M B H to match where M is the cache size and B is the block size. We present a simple algorithm which almost matches this lower bound. The number of cache misses our algorithm causes is