Article

Free access

Generalized sweep methods for parallel computational geometry

Authors:

M. Goodrich,

M. Ghouse,

J. BrightAuthors Info & Claims

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

Pages 280 - 289

https://doi.org/10.1145/97444.97695

Published: 01 May 1990 Publication History

PDF eReader

References

[1]

Abrahamson, K., Dadoun, N., Kirpatrick, D.A., and Przytycka, T., "A Simple Parallel Tree Contraction Algorithm," TR 87-30, Dept. of Comp. Sci., Univ. of British Columbia, 1987.

Digital Library

Google Scholar

[2]

A. Aggarwal, B. Chazelle, L. Gulbas, C. ~)'D~ain$, and C. Yap, "Parallel Computational Geometry," Algorithmica, 3(3), 1988, 293-328.

Digital Library

Google Scholar

[3]

R.J. Anderson and G.L. Miller, "Deterministic Parallel List Ranking," Lecture Notes 319: A WOC 88, Sprlnger-Ver}ag, 1988, 81-90.

Digital Library

Google Scholar

[4]

M.J. Ataliah, R. Cole, and M.T. Goodrich, "Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms," SIAM J. on Comput., 18(3), 1989, 499-532.

Digital Library

Google Scholar

[5]

M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju, "Parallel Algorithms for Evaluating Sequences of Set- Manipulation Operations," Lecture Note8 319: A WOC 88, Sprlnger-Verlag, 1988, 1-10.

Digital Library

Google Scholar

[6]

:I.L. Bentley and D. Wood, "An Optima} Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. on Computera, C-29(7), 1980, 571-576.

Google Scholar

[7]

M. Bern, "Hidden Surface Removal for Rectangles," jth ACM Syrup. on Comp. Geom., 1988, 183-192.

Digital Library

Google Scholar

[8]

R.P. Brent, "The Parallel Evalutation of Genera} Arithmetic Expressions," J. A CM, 21(2), 1974, 201- 206.

Digital Library

Google Scholar

[9]

Chandran, S., and Mount, D., "Shared memory algorithms and the medial axis transform", 1987 IEEE Workahop on Computer Arch.for PAMI.

Google Scholar

[10]

B. Chazelle and L.J. Guibas, "Fractional Cascading: I. A Data Structuring Technique," Algorithmica, 1(2), 133-162.

Google Scholar

[11]

A. Chow, "Parallel Algorithms for Geometric Problems," Ph.D. thesis, Comp. Sci., Univ. of Illlnols, 1980.

Digital Library

Google Scholar

[12]

R. Cole, "Parallel Merge Sort," SIAM J. Comput., 17(4), 1988, 770-785.

Digital Library

Google Scholar

[13]

R, Cole and U. Vishkin, "Approximate Scheduling, Exact Scheduling, and Applications to Paranel Algorithms," ~Tth FOCS, 1986, 478-491.

Google Scholar

[14]

Driscoll, J.R., Sexnak, N., Sleator, D.D., Te~jan, R.E., "Making Data Structures Persistent," 18th STOC, 1986, 109-121.

Digital Library

Google Scholar

[15]

H. Edelsbrunner, Algorithm8 in Combinatorial Geometry, Springer-Verlag, 1987.

Digital Library

Google Scholar

[16]

H. Edels}~runner, H.A. Maurer, F.P. Preparata, A.L. Rosenberg, E. Welzl, and D. Wood, "Stabbing Line Segments," BIT, 22, 1982, 274-281.

Google Scholar

[17]

M.T. Goodrich, "A Polygonal Approach to Hidden- Line Elimination," P.5th Allerton Conference on Comm., Control, and Comput., 1987, 849-858.

Google Scholar

[18]

M.T. Goodrich, "Intersecting Line Segments in Parallel with an Output-Sensitive Number of Processors," 1989 SPAA, 127-137.

Digital Library

Google Scholar

[19]

M.T. Goodxich, "Applying Parallel Processing Techniques to Classification Problems in Constructive Solid Geometry," 18t A CMoSIAM Syrup. Disc. Alg., 1990, 118-128.

Digital Library

Google Scholar

[20]

M.T. Goodrich, M.J. Atallah, and M. Overmars, "An Input-Size/Outpdt-Size r~ade-Off in the Time- Complexity of Rectilinear Hidden Surface Removal," to appear in ICALP '90.

Digital Library

Google Scholar

[21]

M.T. Goodrich and S.R. Kosaxaju, "Sorting on a Paxallel Pointer Machine with Applications to Set Expression Evaluation," 29th FOCS, 1989, 190-195.

Google Scholar

[22]

R.H. G/itlng and T. Ottmann, "New Algorithms For Special Cases of the Hidden Line Elimination Problem," Syrup. on Theo. A apects of Comp. Sci., 1985, 161-171.

Digital Library

Google Scholar

[23]

Kosexaju, S.R., and Delcher, A.L., "Optimal Parallel Evaluation of T~ee-Structured Computations by Raking," Lecture Notes 319: A WOC 88, Springer-Verlag, 1988, 101-110.

Digital Library

Google Scholar

[24]

D.T. Lee and F.P. Preparata, "Computational Geometry--A Survey," IEEE Trana. on Computers, C- 33(12), 1984, 872--1101.

Google Scholar

[25]

W. Lipski, Jr. and F.P. Preparata, "Finding the Contour of a Union of Iso-Oriented Rectangles," J. Algorithms, 1, 1980, 235-246.

Crossref

Google Scholar

[26]

Matias Y., Vishkin U., "On Parallel Hashing and Integer Sorting", Report UMIACS-TR-90-13, Inst. for Adv. Computer Studies, Univ. of Maryland, 1990.

Digital Library

Google Scholar

[27]

K. Mehlhorn, personal communication, October 1989.

Google Scholar

[28]

G.L. Miller and J.H. Reif, "Parallel Tree Contraction and its Application," 26th FOCS, 1985, 478-489.

Google Scholar

[29]

G.L. Miller and S.H. Teng, "Dynamic Parallel Com- 254-263.

Digital Library

Google Scholar

[30]

D.E. Muller and F.P. Prepaxata, "Finding the Intersection of Two Convex Polyhedra," Theo. Comp. Sci., 7(2), 1978, 217-236.

Google Scholar

[31]

M.S. Paterson and F.F. Yao, "Binary Partitions with Applications to Hidden Surface Removal and Solid Modeling," 5th Syrup. on Comp. Geom., 1989, 23-32.

Digital Library

Google Scholar

[32]

F.P. Prepaxata and M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.

Digital Library

Google Scholar

[33]

F.P. Preparata, J.S. Vitter, and M. Yvinec, "Computation of the Axial View of a Set of Isothetic Parallelepipeds," Lab. d'Informatique de L'Ecole Normal Sup&ieure, DEpt. de Math. et d'Info., Report LIENS- 88-1, 1988.

Google Scholar

[34]

J.H. P~eif and S. Sen, "An Efficient Output-Sensitive Hidden-Surface Removal Algorithm and Its PexaUelization," ~th Syrup. on Comp. Geom., 193-200, 1988.

Digital Library

Google Scholar

[35]

A.A.G. Requicha, "Representations for Rigid Solids: Theory, Methods, and Systems," A CM Computin9 Surveys, 12(4), 1980, 437-464.

Digital Library

Google Scholar

[36]

C. R~b, "Parallel line segment intersection reporting," manuscript, 1989.

Google Scholar

[37]

A. Schmitt, "On the Time and Space Complexity of Certain Exact Hidden Line Algorithms," Univ. Kazlsruhe, Faku}t~t fftr Informatik, Report 24/81, 1981.

Google Scholar

[38]

I.E. Sutherland, R.F. Sproull, and R.A. Schumacker, ~A Characterization of Ten Hidden-Surface Algorithms," Computing Surveys, 6(1), March 1974, 1-25.

Digital Library

Google Scholar

[39]

R.E. Taxjan and U. Vishkin, "Finding Biconnected Components and Computing Tree Functions in Loga~ithmlc Parallel Time," SIAM J. Comput., 14, 1985, 862-874.

Google Scholar

[40]

R.B. Tilove, "Set Membership Classification: A Unified Approach to Geometric Intersection Problems," IEEE Trana. on Computerz, C~29(10), 1980, 874-883.

Google Scholar

[41]

R.B. Tilove, "A Null-Object Detection Algorithm for Constructive Solid Geometry," Comm. A CM, 27(7), 1984, 684-694.

Digital Library

Google Scholar

[42]

H. Wagener, "Optimally PaxaUel Algorithms for Convex Hull Determination," manuscript, 1985.

Google Scholar

[43]

Widmayer, P., and Wood, D., "Time and Space- Optimal Contour Computation For a Set of Rectangles", In.fo. Proc. Let., 24, 1987, 335-338.

Digital Library

Google Scholar

[44]

Wood, D., "The Contour Problem For Rectilinear Polygons", Info. Proc. Let., 19, 1984, 1984, 229-236.

Digital Library

Google Scholar

Cited By

View all

Mckenney MFrye RDellamano MAnderson KHarris J(2017)Multi-core parallelism for plane sweep algorithms as a foundation for GIS operationsGeoinformatica10.1007/s10707-016-0277-721:1(151-174)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10707-016-0277-7
Audet SAlbertsson CMurase MAsahara AKnoblock CSchneider MKröger PKrumm JWidmayer P(2013)Robust and efficient polygon overlay on parallel stream processorsProceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2525314.2525352(304-313)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2525314.2525352
McKenney MDe Luna GHill SLowell L(2011)Geospatial overlay computation on the GPUProceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2093973.2094051(473-476)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2093973.2094051
Show More Cited By

Index Terms

Generalized sweep methods for parallel computational geometry

Recommendations

Sweep methods for parallel computational geometry

In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include:General hidden-surface ...
Parallel computational geometry
Abstract
We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive ...
Parallel computation in computational geometry

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

May 1990

417 pages

ISBN:0897913701

DOI:10.1145/97444

Chairman:
F. T. Leighton
Massachusetts Institute of Technology, Cambridge, MA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA90

Sponsor:

Computer Tech Inst.
CTI
SIGACT
SIGARCH
EATCS
IEEE-CS

SPAA90: 2nd Annual ACM Symposium on Parallel Algorithms & Architecture

July 2 - 6, 1990

Island of Crete, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)8

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mckenney MFrye RDellamano MAnderson KHarris J(2017)Multi-core parallelism for plane sweep algorithms as a foundation for GIS operationsGeoinformatica10.1007/s10707-016-0277-721:1(151-174)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10707-016-0277-7
Audet SAlbertsson CMurase MAsahara AKnoblock CSchneider MKröger PKrumm JWidmayer P(2013)Robust and efficient polygon overlay on parallel stream processorsProceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2525314.2525352(304-313)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2525314.2525352
McKenney MDe Luna GHill SLowell L(2011)Geospatial overlay computation on the GPUProceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2093973.2094051(473-476)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1145/2093973.2094051
Goodrich MTamassia R(1997)Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic TriangulationsJournal of Algorithms10.1006/jagm.1995.079723:1(51-73)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.1006/jagm.1995.0797
Banerjee RGoel VMukherjee A(1993)Efficient parallel evaluation of CSG tree using fixed number of processorsProceedings on the second ACM symposium on Solid modeling and applications10.1145/164360.164409(137-146)Online publication date: 1-Jun-1993
https://dl.acm.org/doi/10.1145/164360.164409
Goodrich MTamassia RYap C(1993)Dynamic ray shooting and shortest paths via balanced geodesic triangulationsProceedings of the ninth annual symposium on Computational geometry10.1145/160985.161157(318-327)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/160985.161157
Atallah M(1992)Parallel techniques for computational geometryProceedings of the IEEE10.1109/5.16341080:9(1435-1448)Online publication date: Jan-1992
https://doi.org/10.1109/5.163410
Goodrich MPapadimitriou C(1991)Using approximation algorithms to design parallel algorithms that may ignore processor allocation (preliminary version)Proceedings of the 32nd annual symposium on Foundations of computer science10.1109/SFCS.1991.185439(711-722)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1109/SFCS.1991.185439

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Sweep methods for parallel computational geometry

Parallel computational geometry

Parallel computation in computational geometry