Generalized sweep methods for parallel computational geometry

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generalized sweep methods for parallel computational geometry

Full text

Pdf (1.27 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents

Island of Crete, Greece

Pages: 280 - 289

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

M. Goodrich	Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD
M. Ghouse	Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD
J. Bright	Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD

Sponsors

IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 19, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/97444.97695 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Karl Abrahamson , Norm Dadoun , David G. Kirkpatrick , Teresa M Przytycka, A Parallel Tree Contraction Algorithm, University of British Columbia, Vancouver, BC, Canada, 1987
	2	A. Aggarwal, B. Chazelle, L. Gulbas, C. ~)'D~ain$, and C. Yap, "Parallel Computational Geometry," Algorithmica, 3(3), 1988, 293-328.
	3	R. J. Anderson , G. L. Miller, Deterministic parallel list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	4	M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
	5	M.J. Atallah , M. T. Goodrich , S. R. Kosaraju, Parallel algorithms for evaluating sequences of set manipulation operations (preliminary version), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	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.
	7	M. Bern, Hidden surface removal for rectangles, Proceedings of the fourth annual symposium on Computational geometry, p.183-192, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73412]
	8	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	9	Chandran, S., and Mount, D., "Shared memory algorithms and the medial axis transform", 1987 IEEE Workahop on Computer Arch..for PAMI.
	10	B. Chazelle and L.J. Guibas, "Fractional Cascading: I. A Data Structuring Technique," Algorithmica, 1(2), 133-162.
	11	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	12	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	13	R, Cole and U. Vishkin, "Approximate Scheduling, Exact Scheduling, and Applications to Paranel Algorithms," ~Tth FOCS, 1986, 478-491.
	14	J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12142]
	15	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	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.
	17	M.T. Goodrich, "A Polygonal Approach to Hidden- Line Elimination," P.5th Allerton Conference on Comm., Control, and Comput., 1987, 849-858.
	18	M. T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72950]
	19	Michael T. Goodrich, Applying parallel processing techniques to classification problems in constructive solid geometry, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.118-128, January 22-24, 1990, San Francisco, California, United States
	20	Michael T. Goodrich , Mikhail J. Atallah , Mark H. Overmars, An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.689-702, July 1990, Warwick University, England
	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.
	22	R H Güting , Th. Ottman, New algorithms for special cases of the hidden line elimination problem, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.161-172, December 1985, Saarbru:9Aicken, Germany
	23	S. R. Kosaraju , A. L. Delcher, Optimal parallel evaluation of tree-structured computations by raking (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	24	D.T. Lee and F.P. Preparata, "Computational Geometry--A Survey," IEEE Trana. on Computers, C- 33(12), 1984, 872--1101.
	25	W. Lipski, Jr. and F.P. Preparata, "Finding the Contour of a Union of Iso-Oriented Rectangles," J. Algorithms, 1, 1980, 235-246.
	26	Yossi Matias , Uzi Vishkin, On parallel hashing and integer sorting, University of Maryland at College Park, College Park, MD, 1990
	27	K. Mehlhorn, personal communication, October 1989.
	28	G.L. Miller and J.H. Reif, "Parallel Tree Contraction and its Application," 26th FOCS, 1985, 478-489.
	29	G. Miller , S. Teng, Dynamic parallel complexity of computational circuits, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.254-263, January 1987, New York, New York, United States [doi>10.1145/28395.28423]
	30	D.E. Muller and F.P. Prepaxata, "Finding the Intersection of Two Convex Polyhedra," Theo. Comp. Sci., 7(2), 1978, 217-236.
	31	M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
	32	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	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.
	34	J. H. Reif , S. Sen, An efficient output-sensitive hidden surface removal algorithm and its parallelization, Proceedings of the fourth annual symposium on Computational geometry, p.193-200, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73413]
	35	Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
	36	C. R~b, "Parallel line segment intersection reporting," manuscript, 1989.
	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.
	38	Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
	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.
	40	R.B. Tilove, "Set Membership Classification: A Unified Approach to Geometric Intersection Problems," IEEE Trana. on Computerz, C~29(10), 1980, 874-883.
	41	Robert B. Tilove, A null-object detection algorithm for constructive solid geometry, Communications of the ACM, v.27 n.7, p.684-694, July 1984 [doi>10.1145/358105.358195]
	42	H. Wagener, "Optimally PaxaUel Algorithms for Convex Hull Determination," manuscript, 1985.
	43	Peter Widmayer , Derick Wood, Time- and space-optimal contour computation for a set of rectangles, Information Processing Letters, v.24 n.5, p.335-338, 16 March 1987 [doi>10.1016/0020-0190(87)90159-1]
	44	Derick Wood, The contour problem for rectilinear polygons, Information Processing Letters, v.19 n.5, p.229-236, Nov. 1984 [doi>10.1016/0020-0190(84)90058-9]

CITED BY 3

	Raja P. K. Banerjee , Vineet Goel , Amar Mukherjee, Efficient parallel evaluation of CSG tree using fixed number of processors, Proceedings on the second ACM symposium on Solid modeling and applications, p.137-146, May 19-21, 1993, Montreal, Quebec, Canada
	Mikhail J. Atallah , Michael T. Goodrich , S. Rao Kosaraju, Parallel algorithms for evaluating sequences of set-manipulation operations, Journal of the ACM (JACM), v.41 n.6, p.1049-1088, Nov. 1994
	Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States