Random sampling in geometric optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random sampling in geometric optimization: new insights and applications

Full text

Pdf (816 KB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 91 - 99

Year of Publication: 2000

ISBN:1-58113-224-7

Authors

Bernd Gärtner	Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland
Emo Welzl	Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/336154.336186 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	Ilan Adler , Ron Shamir, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, Mathematical Programming: Series A and B, v.61 n.1, p.39-52, Aug. 11, 1993 [doi>10.1007/BF01582137]
	2	Robert E. Bixby , John W. Gregory , Irvin J. Lustig , Roy E. Marsten , David F. Shano, Very large-scale linear programming: a case study in combining interior point and simplex methods, Operations Research, v.40 n.5, p.885-897, Sept.–Oct. 1992 [doi>10.1287/opre.40.5.885]
	3	V. Chv~tal. Linear Programming. W. H. Freeman, New York, NY, 1983.
	4	K. L. Clarkson. New applications of random sampling in computational geometry. Discrete Comput. Geom., 2:195-222, 1987.
	5	K. L. Clarkson. A bound on local minima of arrangements that implies the upper bound theorem. Discrete Comput. Geom., 10:427-233, 1993.
	6	Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM (JACM), v.42 n.2, p.488-499, March 1995 [doi>10.1145/201019.201036]
	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	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	9	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	10	D. Dubhashi and D. Ranjan. Great(er) expectations. BRICS Newsletter, 5, 1996.
	11	B. G~irtner. Randomized Optimization by Simplex-Type Methods. PhD thesis, Freie Universit~it Berlin, 1995.
	12	Bernd Gärtner, Exact arithmetic at low cost—a case study in linear programming, Computational Geometry: Theory and Applications, v.13 n.2, p.121-139, June 1999 [doi>10.1016/S0925-7721(99)00012-7]
	13	Bernd Gärtner , Sven Schönherr, An efficient, exact, and generic quadratic programming solver for geometric optimization, Proceedings of the sixteenth annual symposium on Computational geometry, p.110-118, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336191]
	14	Bernd Gärtner , Emo Welzl, Linear Programming - Randomization and Abstract Frameworks, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.669-687, February 22-24, 1996
	15	Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
	16	L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992.
	17	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	18	S. Har-Peled. On the expected complexity of random convex hulls. Technical Report 330, School of Math. Sciences, Tel-Aviv University, 1998.
	19	J. Matou~ek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365-384, 1995.
	20	J. Matougek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498-516, 1996.
	21	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, N J, 1994.
	22	A. R~nyi and R. Sulanke. ~Iber die konvexe Hiille yon n zufdllig gew~ihlten Punkten. Z. Wahrscheinlichkeitstheorie, 2:75-84, 1963.
	23	Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
	24	R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor, New Trends in Discrete and Computational Geometry, volume 10 of Algorithms and Combinatorics, pages 37-68. Springer-Verlag, 1993.
	25	R. Seidel. Personal communication, 1996.
	26	Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
	27	E. Welzl. Smallest enclosing disks (balls and ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, volume 555 of Lecture Notes Comput. Sci., pages 359-370. Springer-Verlag, 1991.

CITED BY 2

	Bernd Gärtner , Sven Schönherr, An efficient, exact, and generic quadratic programming solver for geometric optimization, Proceedings of the sixteenth annual symposium on Computational geometry, p.110-118, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	M. Pellegrini, Randomizing combinatorial algorithms for linear programming when the dimension is moderately high, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.101-108, January 07-09, 2001, Washington, D.C., United States