.png){kind=icon}
Return
Scaleable parallel algorithms for lower envelopes with applications
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1998.1478.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper considers a variety of geometric problems based in description of the loir er envelope function, on input sets of size n using a coarse grained multicomputer model consisting of p processors with Omega(n/p) local memory each (i.e., Omega(n/p) memory cells of Theta(log n) bits apiece), where the processors are connected to an arbitrary interconnection network. We give an efficient scaleable parallel algorithm for computation of the lower envelope and use this algorithm to obtain efficient solutions for a variety of geometric problems, including the minimization of the Hausdorff distance between two finite sets on the real line when one is subject to translation; the Common Intersection Problem for vertically convex planar polygons; and several problems in Dynamic Computational Geometry: in which we consider geometric questions for systems of moving objects. All of the algorithms presented are scaleable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scaleability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations. (C) 1998 Academic Press.
Keywords:
parallel algorithms
computational geometry
scaleable algorithms
coarse grained multicomputer
lower envelope
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveHigh prevalence of abnormal eating and weight control practices among U.S. high-school students
PREAI
ShareSave
View more