Linear programming queries revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear programming queries revisited

Full text

Pdf (542 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: 176 - 181

Year of Publication: 2000

ISBN:1-58113-224-7

Author

Edgar A. Ramos

Max-Planck-Institut für Informatik, Saarbrücken, Germany

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): 3, Downloads (12 Months): 16, Citation Count: 1

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/336154.336198 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	H. BrSnnimann, B. Chazelle, and J. Matou~ek. Product range spaces, sensitive sampling, and derandomization. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci., 400-409, 1993.
	2	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 [doi>10.1145/237218.237397]
	3	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Journal of Algorithms, v.21 n.3, p.579-597, Nov. 1996 [doi>10.1006/jagm.1996.0060]
	4	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	5	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]
	6	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]
	7	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	8	D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2 (1987), 127-151.
	9	Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129759]
	10	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Journal of Computer and System Sciences, v.50 n.2, p.203-208, April 1995
	11	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	12	Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
	13	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	14	J. Matou~ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom. 10 (1993), 215-232.
	15	J. Matou~ek, M. Sharir and E. Welzl. A subexponential bound for linear programming. Algorithmica 16 (1996), 498-516.
	16	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	17	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]