Boolean Set Operations on a MIMD Distributed Memory Machine
Chandrajit Bajaj · Purdue e-Pubs (Purdue University System) · 1992
We present an efficient algorithm for Boolean Set operations between two arbitrary manifold polyhedra, on a MIMD distributed memory machine such as as the nCUBE2 or the Intel IPSC860.For two manifold polyhedra with O(n) edges each, our algorithms run in 0(log2 n ) time on an n 2 processor MIMD machine.Our model of computation assumes exact arithmetic on each processor and the ability for any processor PI to communicate an 0(1) size message in 0(1) time to any other processor P2 if PI knows P2'S ID.In this paper we also present a distributed data structure for arbitrary polyhedra on MIMD distributed memory machines.