SOLVING GEOMETRIC PROBLEMS ON A TWO-DIMENSIONAL SYSTOLIC ARRAY.

Systolic algorithms for solving a number of geometric problems on a two-dimensional systolic array algorithms are presented, for segment and rectangle intersection counting as well as an algorithm for constructing the convex hull of a set of n planar points represented by their Cartesian coordinates. An update algorithm for the fixed-size disk placement problem is also given. A subcomputation of the convex hull algorithm required the sort of a set of n elements. It is shown how this can be done in O(n**2**/**3) time on an n**2**/**3 multiplied by n**2**/**3 systolic array.

SOLVING GEOMETRIC PROBLEMS ON A TWO-DIMENSIONAL SYSTOLIC ARRAY. Conference Paper