×

Parallel algorithms for all maximal equally-spaced collinear sets and all maximal regular coplanar lattices. (English) Zbl 0782.68113

Summary: The All Maximal Equally-Spaced Collinear Subset (AMESCS) Problem is defined as follows. Given a set \(P\) of \(n\) points in a Euclidean space \(E^ d\), find all maximal equally-spaced collinear subsets of \(P\). An optimal \(\Theta(n^ 2)\) time sequential solution to the problem is given in A. B. Kahng and G. Robins [Optimal algorithms for extracting spatial regularity in images. Pattern Recognition Lett. 12, 757-764 (1991)]. A related problem is the All Maximal Regularly-Spaced Subsets (AMRSS) Problem, defined as follows. Given a set \(P\) of \(n\) points in \(E^ d\), find all maximal regularly-spaced coplanar subsets of \(P\). An optimal \(O(n^ 3)\) time sequential solution to the problem is given in A. B. Kahng and G. Robins [loc. cit.]. We consider parallel solutions to the AMESCS and AMRSS Problems. Optimal sequential running times of \(O(n^ 2)\) and \(O(n^ 3)\), respectively, make parallel solutions of these problems desirable for large \(n\). While the optimal sequential algorithms of A. B. Kahng and G. Robins [loc. cit.] are dominated by repetitions of a procedure that requires \(\Theta(n)\) time per repetition, and appears inherently sequential, the algorithms we give are quite different. Our parallel algorithms solve both of these problems to within a logarithmic factor of optimality on the Arbitrary CRCW PRAM, and in optimal time on the mesh-connected computer.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI