Computing faces in segment and simplex arrangements

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing faces in segment and simplex arrangements

Full text

Pdf (1.40 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 672 - 682

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Nancy M. Amato	Texas A&M Univ.
Michael T. Goodrich	Johns Hopkins Univ.
Edgar A. Ramos	Univ. of Illinois

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 9

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/225058.225285 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	Pankaj K. Agarwal , Jiří Matoušek , Otfried Schwarzkopf, Computing many faces in arrangements of lines and segments, Proceedings of the tenth annual symposium on Computational geometry, p.76-84, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177548]
	2	Pankaj K. Agarwal, Partitioning arrangements of lines, part II: applications, Discrete & Computational Geometry, v.5 n.6, p.533-573, Sep. 1990 [doi>10.1007/BF02187809]
	3	P. K. Agarwal. Geometric partitioning znd ita applications. Jn J. E. Gnodman, R. Pollack, and W. Steiger, editmx, Computational Geometry: Papersfmm the DIMACS special year. Amer. Math. Sot., 1991.
	4	N.M. Amato, M.T. Goodrich, and E.A. Ramos. Parallel algorithms for higher-dimensional convex hulls. fn Prac. 35th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 93), pages 683-694,1994.
	5	Ivan J. Balaban, An optimal algorithm for finding segments intersections, Proceedings of the eleventh annual symposium on Computational geometry, p.211-219, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220302]
	6	J. L. Bentley znd T. A. Ottmann. Algorithrna forreportingand counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979.
	7	Hen+ Br&mimann,Bemard Chzzelle, znd JiJi Mztmriek. Product rsnge spaces, sensitive sampling, and derzndomization. fn Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS 93), pages 400-409,1993.
	8	Bernard Chazelle, Reporting and counting segment intersections, Journal of Computer and System Sciences, v.32 n.2, p.156-182, April 1986 [doi>10.1016/0022-0000(86)90025-5]
	9	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	10	B. Chazelle. An optimal convex hull algorithm in zny fixed dimension. Di$crete Compu/. Geom., 10:377=IO9, 1993.
	11	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
	12	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
	13	Ka Wong Chong , Tak Wah Lam, Finding connected components in O(log n loglog n) time on the EREW PRAM, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.11-20, January 25-27, 1993, Austin, Texas, United States
	14	K. L. Clarkson. Randomized geometric algorithms. Jn D.-Z. Du and F. K. Hwang, editorz, Computing in Euclidean Geometry, volume 1 of Lecture Notes Series on Cornputirrg, pages 117-162. World Scientific, Singapore, 1992.
	15	K. L. Clarkson, R. Cole, and R. E. Tarjan. Errztum: Randomized parallel algo-rithms for trapezoidal diagrsms. Internat. J. Comput. Geom. AppL, 2(3):341 -343, 1992.
	16	K. L. Clarkson, R. Cole, and R. E. Tarjsn. Randomized parzllel algorithms for trapezoidal diagrams. Jniernat. J. Comput. Geom. AppL, 2(2):1 17-1 33,1992.
	17	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]
	18	Mark de Berg , Katrin Dobrindt , Otfried Schwarzkopf, On lazy randomized incremental construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.105-114, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195113]
	19	Marc de Berg , Leonidas J. Guibas , Dan Halperin, Vertical decompositions for triangles in 3-space, Proceedings of the tenth annual symposium on Computational geometry, p.1-10, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177427]
	20	Michael T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, SIAM Journal on Computing, v.20 n.4, p.737-755, Aug. 1991 [doi>10.1137/0220047]
	21	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161002]
	22	M. T. Goodrich, S. Shauck, and S. Guha. Parallel methods for visibility and ahortmt path problems in simple polygnns. Algoritkmica, 8:461-486,1992.
	23	M. T. Gondrich, S. Shauck, znd S. Guba. Addendum to "parallel methods for visibility and shortest path problems in simple pnlygons". Algorifhmica, 9:5 15- 516,1993.
	24	L. J. Guibas, On the general motion-planning problem with two degrees of freedom, Discrete & Computational Geometry, v.4 n.5, p.491-521, 1989 [doi>10.1007/BF02187744]
	25	Shay Halperin , Uri Zwick, An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181017]
	26	A. Joffe. On a set of almost deterministic k-independentrandom variables. Annafs of Probability, 2:161-162, 1974.
	27	Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
	28	J. Matmr3ek. Epsilon-nets snd computational geemetry. Jn J. Path, editer, NW Trends in Discrete and Computational Geome~, vohnne 10 of Algorithm and Combinatorics, pagez 69-89. Springer-Verlag, 1993.
	29	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.478-484, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167217]
	30	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	31	K. Mehlhorn , M. Sharir , E. Welzl, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, Computational Geometry: Theory and Applications, v.3 n.4, p.235-246, Sept. 1993 [doi>10.1016/0925-7721(93)90011-T]
	32	J. S. B. Mitchell. On computing a single face in m armngementof line segmentx. Manuscript, School Oper. Res. Jndust. Engrg., Cornell Univ., Ithaca, NY, July 1990.
	33	K. Mulmuley. A fast planar partition algnrhhm, I. In Pmt. 29th Annu. lEEE Sympos. Found. Comput. Sci., pages 580-589, 1988.
	34	K. Mulrnuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, New York, 1993.
	35	Marco Pellegrini, On point location and motion planning among simplices, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.95-104, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195112]
	36	R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
	37	John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
	38	Jnbn H. Reif znd Sandeep Sen. Optimal randomized parallel algorithms for computational geometry. Algotithmica, 7(1):91-1 17,1992.
	39	C. Rub. Computing interjections snd arrangements for red-blue curve segments in parallel. fn Proc. 4th Canad. Com Comput. Georn., pages 115-120,1992.
	40	Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]
	41	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

CITED BY 9

	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France
	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France
	A. Crauser , P. Ferragina , K. Mehlhorn , U. Meyer , E. Ramos, Randomized external-memory algorithms for some geometric problems, Proceedings of the fourteenth annual symposium on Computational geometry, p.259-268, June 07-10, 1998, Minneapolis, Minnesota, United States
	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	Edgar A. Ramos, On range reporting, ray shooting and k-level construction, Proceedings of the fifteenth annual symposium on Computational geometry, p.390-399, June 13-16, 1999, Miami Beach, Florida, United States
	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.705-706, January 09-11, 2000, San Francisco, California, United States
	Edgar A. Ramos, Deterministic algorithms for 3-D diameter and some 2-D lower envelopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.290-299, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Esther M. Arkin , Joseph S. B. Mitchell , Jack Snoeyink, Capturing crossings: Convex hulls of segment and plane intersections, Information Processing Letters, v.107 n.5, p.194-197, August, 2008