Efficient parallel computation of arrangements of hyperplanes in d dimensions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel computation of arrangements of hyperplanes in d dimensions

Full text

Pdf (845 KB)

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: 290 - 297

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

Torben Hagerup	Fachbereich 10, Informatik, Universität des Saarlandes, D-6600 Saarbrücken
H. Jung	Sektion Mathematik, Humboldt-Universität Berlin, PF 1297, DDR-1086, Berlin
E. Welzl	Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33

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): 5, Downloads (12 Months): 23, Citation Count: 2

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.97696 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	A.Aggarwal, B.Chazelle, L.Guibas, C.O'Dunlaing, C.Yap, Parallel Computational Geometry. Algorithmica 3 (1988), 293-327
	2	R. J. Anderson , G. L. Miller, Deterministic parallel list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	3	Mikhail J. Atallah , Hubert Wagener , Danny Z. Chen, An optimal parallel algorithm for the visibility of a simple polygon from a point, Journal of the ACM (JACM), v.38 n.3, p.515-532, July 1991 [doi>10.1145/116825.116827]
	4	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]
	5	B.Chazelle, tt.Edelsbrunner, An optimal algorithm for intersecting line segments in the plane. Proc. 29th Ann. IEEE Symp. on Found. of Computer Sci. 1988, 590-600
	6	K.L.Clarkson, New application of random sampiing in computational geometry. Discrete Cornput. Geom. 2 (1987), 195-222
	7	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	8	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	9	R. Cole , U. Vishkin, Optimal parallel algorithms for expression tree evaluation and list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	10	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	11	H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
	12	H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73406]
	13	H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
	14	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	15	B.Griinbaum, Convex Polytopes. John Wiley & Sons, London, 1967
	16	D.Haussler, E.Welzl, e-nets and simplex range queries. Discrete Comput. Geom. 2 (1987), 127-151
	17	C.Kruskal, L.Rudolph, M.Snir, The power of parariel prefix. Proc. 1985 IEEE int. Cone on Parallel P roc., 180-185
	18	J. H. Reif , S. Sen, Polling: a new randomized sampling technique for computational geometry, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.394-404, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73045]
	19	Y.Shiloach, U.Vishkin, An O(logn)parallel connectivity algorithm. J.Algorithms 3 (1982), 57-67
	20	C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

CITED BY 2

	Michael T. Goodrich, Constructing arrangements optimally in parallel (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.169-179, July 21-24, 1991, Hilton Head, South Carolina, United States
	Kenneth L. Clarkson , Richard Cole , Robert E. Tarjan, Randomized parallel algorithms for trapezoidal diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.152-161, June 10-12, 1991, North Conway, New Hampshire, United States