More Web Proxy on the site http://driver.im/

Article

Free access

On the parallel decomposability of geometric problems

Authors:

J. J. TsayAuthors Info & Claims

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

Pages 104 - 113

https://doi.org/10.1145/73833.73845

Published: 05 June 1989 Publication History

Abstract

There is a large and growing body of literature concerning the solution of geometric problems on mesh-connected arrays of processors [5,9,14,17]. Most of these algorithms are optimal (i.e., run in time Ο(n^1/d) on a d-dimensional n-processor array), and they all assume that the parallel machine is trying to solve a problem of size n on an n-processor array. What happens when we have parallel machine for efficiently solving a problem of size p, and we are interested in using it to solve a problem of size n < p? The answer to that question has to do with a fundamental, and yet (at least so far) little-studied property of geometric problems: their parallel-decomposability. More specifically, given that a problem of size p can be solved on a parallel machine P faster by a factor of (say) s(p) than on a RAM alone, then that problem is fully parallel-decomposable for P if a RAM to which the parallel machine P is attached can solve arbitrarily large problems with a speedup of also s(p) when compared to a RAM alone. The issue has been settled for the sorting problem when P is a linear systolic array [1,2,3,11]. Here we show that many geometric problems are fully parallel-decomposable for (multidimensional) mesh-connected arrays of processors.

References

[1]

A. Aggarwal and J. S. Vitter, The Input/Qutput Complexity of Sorting and Related Problems, CACM, pp. 1116-1127, Sept. 1988.

Digital Library

[2]

M. J. Atallah and G. N. Frederickson and S. R. Kosaraju, Sorting With Efficient Use of Special- Purpose Sorters, IPL, pp. 13-15, 1988.

Digital Library

[3]

R. Beige1 and J. Gill, Sorting tt Objects with a k-sorter, TRCS, The Johns Hopkins University, Apr. 1987.

[4]

J. Bentley, Multidimensional divide-and-conquer CACM, pp. 214-229, Apr. 1980.

Digital Library

[5]

B. Chazelle, Computational Geometry on a Systolic Chip, IEEE Trans. on Computers, pp. 774- 785, Sept. 1984.

Digital Library

[6]

G.N. Frederickson and D.B. Johnson, The Complexity of Selection and Ranking in X + Y and Matrices with Sorted Columns, JCSS, pp. 197- 208, 1982.

[7]

M. Goodrich, Efficient Parallel Techniques for Computational Geometry, Ph.D. Thesis, Dept. of Computer Science, Purdue University, 1987.

Digital Library

[8]

R.H. Giiting, Optimal Divide-and-Conquer to Compute Measure and Contour for a Set of Iso- Rectangles, Acta Informatica, pp. 271-291, 1984.

[9]

C. S. Jeong and D. T. Lee, Parallel Geometric Algorithms on a Mesh Connected Computer, TR, 87-0%FC-01, Dept. EE/CS, Northwestern Univ., 1987. To appear in Algorithmica.

[10]

S.R. Kosaraju and M.J. Atallah, Optimal Simulations Between Meshed-Connected Arrays of Processors, JACiU, pp. 635-650, July 1988.

Digital Library

[11]

D.T. Lee and H. Chang and C.K. Wong, An onchip compare steer bubble sorter, IEEE Trans. Computers, pp. 396-405, 1981.

[12]

D.T. Lee and F.P. Preparata, Computational Geometry-A Survey, IEEE Trans. on Computers, pp. 872-1101, 1984.

[13]

C. Mead and L. Conway, Introduction to VLSI System, Addison-Wesley, 1980.

Digital Library

[14]

R. Miller and Q. F. Stout, Mesh Computer Algorithms for Computational Geometry, TR 86-18, Dept. of CS, SUNY at Buffalo, 1986.

[15]

H. Mueller, Sorting Numbers Using Limited Systolic Coprocessors, IPL, pp. 351-354, 1987.

Digital Library

[16]

F.P. Preparata and MI. Shamos, Computational Geometry, Springer-Verlag, 1985.

Digital Library

[17]

Z.C. Shih and G.H. Chen and R.C.T. Lee, Systolic Algorithms to Examine All Pairs of Elements, CACM, pp. 161-167, Feb. 1987.

Digital Library

Cited By

Diallol MFerreira ARau-Chaplin A(2005)Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi DiagramSTACS 9810.1007/BFb0028576(399-409)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0028576
Diallo MFerreira ARau-Chaplin AUbéda S(1999)Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained MulticomputersJournal of Parallel and Distributed Computing10.1006/jpdc.1998.150356:1(47-70)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1006/jpdc.1998.1503
Dehne FDeng XDymond PFabri AKhokhar A(1997)A Randomized Parallel Three-Dimensional Convex Hull Algorithm for Coarse-Grained MulticomputersTheory of Computing Systems10.1007/s00224000006730:6(547-558)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1007/s002240000067
Show More Cited By

Index Terms

On the parallel decomposability of geometric problems

Recommendations

On the parallel-decomposability of geometric problems
Abstract
There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n^1/d) on ad-dimensionaln-processor array), and they all ...
Coarse-Grained Parallel Geometric Search

We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O(...
Parallel algorithms for geometric problems on networks of processors
SPDP '93: Proceedings of the 1993 5th IEEE Symposium on Parallel and Distributed Processing

In this paper, we present algorithms for solving several basic geometric problems of size n in a network of p processors each with O(n/p) local memory. Our algorithms achieve the best possible (up to a constant factor) time bound in hypercubic parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '89: Proceedings of the fifth annual symposium on Computational geometry

June 1989

401 pages

ISBN:0897913183

DOI:10.1145/73833

Chairman:
Kurt Mehlhorn

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
292
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)11

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Diallol MFerreira ARau-Chaplin A(2005)Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi DiagramSTACS 9810.1007/BFb0028576(399-409)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0028576
Diallo MFerreira ARau-Chaplin AUbéda S(1999)Scalable 2D Convex Hull and Triangulation Algorithms for Coarse Grained MulticomputersJournal of Parallel and Distributed Computing10.1006/jpdc.1998.150356:1(47-70)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1006/jpdc.1998.1503
Dehne FDeng XDymond PFabri AKhokhar A(1997)A Randomized Parallel Three-Dimensional Convex Hull Algorithm for Coarse-Grained MulticomputersTheory of Computing Systems10.1007/s00224000006730:6(547-558)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1007/s002240000067
Dehne FDeng XDymond PFabri AKhokhar ALeiserson C(1995)A randomized parallel 3D convex hull algorithm for coarse grained multicomputersProceedings of the seventh annual ACM symposium on Parallel algorithms and architectures10.1145/215399.215410(27-33)Online publication date: 20-Jul-1995
https://dl.acm.org/doi/10.1145/215399.215410
Ferreira ARau-Chaplin AUeda S(1995)Scalable 2d convex hull and triangulation algorithms for coarse grained multicomputersProceedings.Seventh IEEE Symposium on Parallel and Distributed Processing10.1109/SPDP.1995.530733(561-568)Online publication date: 1995
https://doi.org/10.1109/SPDP.1995.530733
Dehne FFabri ARau-Chaplin AYap C(1993)Scalable parallel geometric algorithms for coarse grained multicomputersProceedings of the ninth annual symposium on Computational geometry10.1145/160985.161154(298-307)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/160985.161154
(1992)BibliographyIntroduction to Parallel Algorithms and Architectures10.1016/B978-1-4832-0772-8.50008-X(785-801)Online publication date: 1992
https://doi.org/10.1016/B978-1-4832-0772-8.50008-X

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents