The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are as follows: A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in $O(\log\log N)$ communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.

Holography is a method for three dimensional imaging of objects. We present an approach for the generation of holograms, exploiting standard graphics rendering methods and hardware. We focus on the visualization of objects composed of line segments, which allow for certain simplifications, and thus hologram generation speedup. Our method is based on the derivation of a holographic geometric equivalent of the object to be imaged. In this equivalent, the object is represented as a set of geometric primitives combined with precomputed textures. The equivalent is built up under prescribed conditions, thus simulating certain wave characteristics. The hologram of the object to be imaged is gained just by rendering its holographic geometric equivalent. Problems of achieving the necessary resolution of the output hologram are addressed.

The author proposes an optimal parallel algorithm for computing the convex hull of a simple polygon. The algorithm achieves a runtime of O(log log n) using O(n/log log n) processors of a CRCW-PRAM. The data structure representing the convex hull is not the standard one, i.e. an array storing the vertices of the hull in clockwise order. Indeed, a lower bound of Omega (log n/log log n) on the runtime for any algorithm employing a polynomial number of processors and computing the array-representation is known. Nevertheless, the representation is adequate for further parallel processing; standard queries like computing the intersection of the hull with a given line, etc., can be answered in time O(log n/(log p+1)+1) using p processors. In addition subchain hull queries are supported optimally in time O(log k/(log p+1)+1), where k is the length of the subchain. The algorithm can easily be adapted to other hull-like structures for simple polygons; as e.g. the orthogonal hull, and the visibility region from a point under various definitions of visibility.>

article Free Access Share on An optimal parallel algorithm for the visibility of a simple polygon from a point Authors: Mikhail J. Atallah Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile , Hubert Wagener Technische Univ., Berlin, Germany Technische Univ., Berlin, GermanyView Profile , Danny Z. Chen Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile Authors Info & Claims Journal of the ACMVolume 38Issue 3July 1991 pp 515–532https://doi.org/10.1145/116825.116827Published:01 July 1991Publication History 19citation554DownloadsMetricsTotal Citations19Total Downloads554Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

No abstract available.