Efficient randomized algorithms for some geometric optimization problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient randomized algorithms for some geometric optimization problems

Full text

Pdf (1.09 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the eleventh annual symposium on Computational geometry table of contents

Vancouver, British Columbia, Canada

Pages: 326 - 335

Year of Publication: 1995

ISBN:0-89791-724-3

Authors

Pankaj K. Agarwal	Department of Computer Science, Box 90129, Duke University, Durham, NC
Micha Sharir	School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 14, Citation Count: 4

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/220279.220314 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 , Boris Aronov , Micha Sharir, Computing envelopes in four dimensions with applications, Proceedings of the tenth annual symposium on Computational geometry, p.348-358, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178081]
	2	Pankaj K. Agarwal , Otfried Schwarzkopf , Micha Sharir, The overlay of lower envelopes in three dimensions and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.182-189, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220299]
	3	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
	4	A. Aggarwal , S. Suri, Computing the longest diagonal of a simple polygon, Information Processing Letters, v.35 n.1, p.13-18, June 1990 [doi>10.1016/0020-0190(90)90167-V]
	5	H. BrSnnimann and B. Chazelle, Optimal slope selection via cuttings, Proc. 6th Canadian Conf. on Computational Geometry, 1994, 99-103.
	6	B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, width, closest line pair, and parametric searching, Discrete Comput. Geom. 10 (1993), 183-196.
	7	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.179-193, July 11-15, 1989
	8	B. Chazelle , M. Sharir, An algorithm for generalized point location and its applications, Journal of Symbolic Computation, v.10 n.3-4, p.281-309, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80065-X]
	9	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	10	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]
	11	M. Dillencourt, D. Mount, and N. Netanyahu, A randomized algorithm for slope selection, int. J. Comput. Geom. and Appls 2 (1992), 1-27.
	12	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]
	13	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]
	14	H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi, Roundness algorithms using the Voronoi diagrams, First Canadian Conf. on Computational Geometry, 1989.
	15	D. Halperin and M. Sharir, New bounds for lower envelopes in 3 dimensions, with applications to visibility in terrains, Discrete Comput. Geom. 12 (1994), 313-326.
	16	D. Haussler and E. Welzl, e-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127-151.
	17	M. E. Houle , G. T. Toussaint, Computing the Width of a Set, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.761-765, September 1988 [doi>10.1109/34.6790]
	18	Matthew J. Katz , Micha Sharir, Optimal slope selection via expanders, Information Processing Letters, v.47 n.3, p.115-122, Sept. 14, 1993 [doi>10.1016/0020-0190(93)90234-Z]
	19	Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161137]
	20	Jiři Matoušek, Randomized optimal algorithm for slope selection, Information Processing Letters, v.39 n.4, p.183-187, Aug. 30, 1991 [doi>10.1016/0020-0190(91)90177-J]
	21	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	22	M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom. 12 (1994), 327-345.
	23	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	24	M. Staid and R. Janardan, On the width and roundness of a set of points in the plane, manascript, 1995.

CITED BY 4

	Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Pankaj K. Agarwal , Otfried Schwarzkopf , Micha Sharir, The overlay of lower envelopes in three dimensions and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.182-189, June 05-07, 1995, Vancouver, British Columbia, Canada
	Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
	Young J. Kim , Ming C. Lin , Dinesh Manocha, Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion, IEEE Transactions on Visualization and Computer Graphics, v.10 n.2, p.152-163, March 2004