Fixed-dimensional linear programming queries made easy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fixed-dimensional linear programming queries made easy

Full text

Pdf (695 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 284 - 290

Year of Publication: 1996

ISBN:0-89791-804-5

Author

Timothy M. Chan

Center for Geometric Computing, Department of Computer Science, Johns Hopkins University, Baltimore, MD

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

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

	AES95	Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications, Proceedings of the eleventh annual symposium on Computational geometry, p.39-50, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220284]
	AM93	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, SIAM Journal on Computing, v.22 n.4, p.794-806, Aug. 1993 [doi>10.1137/0222051]
	AM95	P.K. Agarwal and J. Matou~ek. }Dynamic halfspace range reporting and its applications. Algorithmica, 13:325-345, 1995.
	AS95	Pankaj K. Agarwal , Micha Sharir, Efficient randomized algorithms for some geometric optimization problems, Proceedings of the eleventh annual symposium on Computational geometry, p.326-335, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220314]
	AvKO93	Pankaj K. Agarwal , Marc van Kreveld , Mark Overmars, Intersection queries in curved objects, Journal of Algorithms, v.15 n.2, p.229-266, Sept. 1993 [doi>10.1006/jagm.1993.1040]
	BCM93	H. BrSnnimann, B. Chazelle, and J. Matoufiek. Product range spaces, sensitive sampling, and derandomization, in Proc. 3jth JrEEE Sympos. Found. Comput. Sci., pages 400-409, 1993.
	CG86	B. Chazelle and L. J. Guibas. Fractional cascading Ih Applications. Algorithmlica, 1:163-191, 1986.
	Cha95	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 [doi>10.1145/220279.220281]
	Cla95	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]
	CM93	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	DK90	David P. Dobkin , David G. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.400-413, July 1990, Warwick University, England
	DMN92	M. DiUencourt, D. Mount, and N. Netanyahu. A randomized algorithm for slope selection. Int. J. Comput. Geom. Appl., 2:1-27, 1992.
	ESZ94	Alon Efrat , Micha Sharir , Alon Ziv, Computing the smallest k-enclosing circle and related problems, Computational Geometry: Theory and Applications, v.4 n.3, p.119-136, July 1994 [doi>10.1016/0925-7721(94)90003-5]
	HW87	D. Haussler and E. Welzl. e-nets and simplex range queries. Discrete Comput. Geom., 2'127- 151, 1987.
	Mat91	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]
	Mat92a	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	Mat92b	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]
	Mat93a	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	Mat93b	J. Matou~ek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10:159-182, 1993.
	Mat94	Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]
	Mat95a	Jiří Matoušek, On enclosing k points by a circle, Information Processing Letters, v.53 n.4, p.217-221, Feb. 24, 1995 [doi>10.1016/0020-0190(94)00190-A]
	Mat95b	J. Matou~ek. On geometric optimization with few violated constraints. Discrete Comput. Geom., 14:365-384, 1995.
	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]
	MS93	J. Matou~ek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215-232, 1993.
	Mul93	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.j., 1993.
	Pug90	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
	Sei91	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]
	ST95	Elmar Schömer , Christian Thiel, Efficient collision detection for moving polyhedra, Proceedings of the eleventh annual symposium on Computational geometry, p.51-60, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220285]
	SW92	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
	Tol92	S. Toledo. Maximizing non-linear concave functions in fixed dimension. In Proc. 33rd IEEE Sympos. Found. Comput. Sci., pages 696-685, 1992.

CITED BY 10

	Timothy M. Chan, Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Proceedings of the sixteenth annual symposium on Computational geometry, p.300-309, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Edgar A. Ramos, Linear programming queries revisited, Proceedings of the sixteenth annual symposium on Computational geometry, p.176-181, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	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
	Jeff Erickson, Space-time tradeoffs for emptiness queries (extended abstract), Proceedings of the thirteenth annual symposium on Computational geometry, p.304-313, June 04-06, 1997, Nice, France
	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
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Timothy M. Chan, Geometric applications of a randomized optimization technique, Proceedings of the fourteenth annual symposium on Computational geometry, p.269-278, June 07-10, 1998, Minneapolis, Minnesota, United States
	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
	Peyman Afshani , Timothy M. Chan, On approximate range counting and depth, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea