We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
CONVEX POLYGON PROBLEMS ON MESHES WITH MULTIPLE BROADCASTING.
- Authors
BHAGAVATHI, D.; OLARIU, S.; SCHWING, J. L.; ZHANG, J.
- Abstract
We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ( n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.
- Publication
Parallel Processing Letters, 1992, Vol 2, Issue 2/3, p249
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626492000386