Computing Convex Hulls Using Smart Pixels
Paul Accisano · 2010
We consider a problem domain consisting of a quadratic grid of n “smart pixels ” which observe a black-and-white image. Each of these smart pixels can communi-cate with its direct neighbors and perform simple com-putations. Contiguous groups of black pixels form ob-jects on the grid. We present a deterministic algorithm to compute the convex hulls of all objects on the pixel grid simultaneously in time O( n). 1