SQUARE MESHES ARE NOT OPTIMAL FOR CONVEX-HULL COMPUTATION

Recently it has been noticed that for semigroup computations and for s election rectangular meshes with multiple broadcasting yield faster al gorithms than their square counterparts. The contribution of this pape r is to provide yet another example of a fundamental problem for which this phenomenon occurs. Specifically, we show that the problem of com puting the convex hull of a set of n sorted points in the plane can be solved in O(n(1/8) log(3/4) n) time on a rectangular mesh with multip le broadcasting of size n(3/3) log(1/4) n x n(5/8)/log(1/4) n. The fas test previously-known algorithms on a square mesh of size root n x roo t n run in O(n(1/6)) time in case the n points are pixels in a binary image, and in O(n(1/6) log(2/3) n) time for sorted points in the plane .