Multiple criteria BSR: an implementation and applications to computational geometry problems
Akl, Stojmenovic · 1994
Provides a detailed description of a BSR (broadcasting with selective reduction) implementation that allows each datum to be tested for its satisfaction of k criteria, where k/spl ges/1. It also shows how a number of computational geometric problems can be solved on a multiple criteria BSR in constant time. These problems include finding the measure of the union of a set of intervals, computing the Voronoi diagram, reporting the intersections of two convex polygons (one criterion), counting intersections of isothetic line segments, vertical segment visibility (three criteria), maximal elements in d dimensions (d-1 criteria), ECDF searching, 2-set dominance counting and rectangle containment in d dimensions (d criteria), rectangle enclosure and intersection counting in d dimensions (2d criteria). The constant time solutions presented are the first such solutions for the problems addressed and the number of processors used. Furthermore, these solutions allow us to illustrate effectively the power and elegance of BSR as shown by the conciseness and simplicity of the algorithms it affords.>