Linear optimization queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear optimization queries

Full text

Pdf (1.11 MB)

Source

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

Berlin, Germany

Pages: 16 - 25

Year of Publication: 1992

ISBN:0-89791-517-8

Authors

Jiří Matoušek
Otfried Schwarzkopf

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): 9, Downloads (12 Months): 28, Citation Count: 12

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/142675.142683 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.

	AM91	K P Agarwal , Jiri Matousek, Dynamic Half-Space Range Reporting and Its Application, Duke University, Durham, NC, 1991
	AM92	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
	CF90	B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Com. binatorica, 10(3):229-249, 1990.
	Cla86	K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
	Cla88a	K. Clarkson. Las Vegas algorithm for linear programming when the dimension is small. In Proc. 29th IEEE Symposium on Foundatzons of Computer Science, pages 452-457, 1988.
	Cla88b	K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
	CM89	E. Cohen , N. Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.523-534, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73057]
	Col87	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	CSW90	Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
	CSY87	Richard Cole , Micha Sharir , Chee K Yap, On k-hulls and related problems, SIAM Journal on Computing, v.16 n.1, p.61-77, Feb. 1987 [doi>10.1137/0216005]
	Dye86	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	Ede87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	Epp91	David Eppstein, Dynamic three-dimensional linear programming, Proceedings of the 32nd annual symposium on Foundations of computer science, p.488-494, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185410]
	GSC87	L. J. Guibas , J. Stolfi , K. L. Clarkson, Solving related two- and three-dimensional linear programming problems in logarithmic time, Theoretical Computer Science, v.49 n.1, p.81-84, Jan. 1987 [doi>10.1016/0304-3975(87)90101-0]
	HW87	D. Haussler and E. Welzl. e-nets and simplex range queries. Discrete ~4 Computational Geometry, 2:127-151, 1987.
	Mat91a	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	Mat91b	Jiří Matoušek, Efficient partition trees, Proceedings of the seventh annual symposium on Computational geometry, p.1-9, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109649]
	Mat91c	Jiří Matoušek, Reporting points in halfspaces, Proceedings of the 32nd annual symposium on Foundations of computer science, p.207-215, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185370]
	Mat91d	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	MS91	J. Matou~ek and O. Schwarzkopf. Linear optimization queries. Tech. Report B 91-19, Freie Universit~t Berlin, 1991.
	Meg83	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]
	Meg84	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]
	Meh85	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	Mul91	Ketan Mulmuley, Randomized multidimensional search trees: lazy balancing and dynamic shuffling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.180-196, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185368]
	NPT90	Carolyn Habit Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.377-387, January 22-24, 1990, San Francisco, California, United States
	PH77	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	Sch91	O. Schwarzkopf. On the Post Office Problem. Manuscript, 1991.
	Sch92	Otfried Schwarzkopf, Ray shooting in convex polytopes, Proceedings of the eighth annual symposium on Computational geometry, p.286-295, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142734]
	Sei86	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	Sei90	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]
	SW90	R. Seidel and E. Welzl. Private communication, May 1990.

CITED BY 12

	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada
	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada
	Takeshi Tokuyama, Minimax parametric optimization problems and multi-dimensional parametric searching, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.75-83, July 2001, Hersonissos, Greece
	Timothy M. Chan, Deterministic algorithms for 2-d convex programming and 3-d online linear programming, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.464-472, January 05-07, 1997, New Orleans, Louisiana, United States
	Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, ACM SIGMOD Record, v.29 n.2, p.391-402, June 2000
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003
	Hervé Brönnimann , Timothy M. Chan , Eric Y. Chen, Towards in-place geometric algorithms and data structures, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States
	Takeshi Tokuyama, Efficient algorithms for the minimum diameter bridge problem, Computational Geometry: Theory and Applications, v.24 n.1, p.11-18, January 2003
	Timothy M. Chan, A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1196-1202, January 22-26, 2006, Miami, Florida