Convexity Problems on Meshes with Multiple Broadcasting

The purpose of this work is to present simple time-optimal algorithms for a number of convexity-related problems on meshes with multiple broadcasting. More specifically, we show that with an n- vertex convex polygon P as input, the tasks of computing the perimeter, the area, the diameter, the width, the modality, the smallest-area enclosing rectangle, and the largest-area inscribed triangle sharing an edge with P , can be solved in O(log n) time on a mesh with multiple broadcasting of size n \Theta n. Furthermore, this is proved time-optimal in this model of computation. Similarly, we show that with two n-vertex convex polygons P and Q as input, the tasks of detecting whether P lies inside Q and of computing the maximum distance between P and Q can be solved in O(log n) time, which turns out to be time-optimal. We further show that in case P and Q are separable, task of computing the minimum distance between P and Q can be performed in O(1) time on a mesh with multiple broadcasting..