Geometric applications of a randomized optimization technique

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric applications of a randomized optimization technique

Full text

Pdf (1.31 MB)

Source

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

Minneapolis, Minnesota, United States

Pages: 269 - 278

Year of Publication: 1998

ISBN:0-89791-973-4

Author

Timothy M. Chan

Dapartment of Mathematics and Computer Science, University of Miami, Coral Gables, FL

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): 18, Citation Count: 5

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/276884.276915 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 , 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]
	2	P. K. Agarwal and M. Shadr. Efficient randomized algorithms for some geometric optimization problems. Discrete Cornput. Geom., 16:317-337, 1996.
	3	K P Agarwal , Micha Sharir, Efficient Randomized Algorithms for Some Geometric Optimization, Duke University, Durham, NC, 1995
	4	Pankaj K. Agarwal , Micha Sharir , Emo Welzl, The discrete 2-center problem, Proceedings of the thirteenth annual symposium on Computational geometry, p.147-155, June 04-06, 1997, Nice, France [doi>10.1145/262839.262921]
	5	Alok Aggarwal , Hiroshi Imai , Naoki Katoh , Subhash Suri, Finding k points with minimum diameter and related problems, Journal of Algorithms, v.12 n.1, p.38-56, March 1991 [doi>10.1016/0196-6774(91)90022-Q]
	6	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	7	B. K. Bhattachaxya and H. E1Gindy. Biased search and k-point clustering. In Proc. 9th Ganad. Conf. Comput. Geom., 1997.
	8	H. BrSnnimann and B. Chazelle. Optimal slope selection via cuttings. In Proc. 6th Canad. Conf. Cornput. Geom., pages 99-103, 1994.
	9	H. BrSnnimann, B. Chazelle, and 3. Matou#ek. Product range spaces, sensitive sampling, and derandomization. In Proc. 3Jth IEEE Syrnpos. Found. Cornput. Sci., pages 400-409, 1993.
	10	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]
	11	T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Corn. put. Geom., 16:369-387, 1996.
	12	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	13	B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Shax#. Diameter, width, closest line pair and parametric searching. Discrete Cornput. Geom., 10:183-196, 1993.
	14	L. Paul Chew , Dorit Dor , Alon Efrat , Klara Kedem, Geometric Pattern Matching in d-Dimensional Space, Proceedings of the Third Annual European Symposium on Algorithms, p.264-279, September 25-27, 1995
	15	L. Paul Chew , Michael T. Goodrich , Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg , Dina Kravets, Geometric pattern matching under Euclidean motion, Computational Geometry: Theory and Applications, v.7 n.1-2, p.113-124, Jan. 1997 [doi>10.1016/0925-7721(95)00047-X]
	16	L. Paul Chew , Klara Kedem, Improvements on Geometric Pattern Matching Problems, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.318-325, July 08-10, 1992
	17	K. L. Clarkson. New applications of random sampling in computational geometry. Discrete Cornput. Geom., 2:195-222, 1987.
	18	K. L. Clarkson. Algorithms for the minimum diameter of moving points and for the discrete 1-center problem. Manuscript, 1997.
	19	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]
	20	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]
	21	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	22	Amitava Datta , Hans-Peter Lenhof , Christian Schwarz , Michiel Smid, Static and dynamic algorithms for k-point clustering problems, Journal of Algorithms, v.19 n.3, p.474-503, Nov. 1995 [doi>10.1006/jagm.1995.1048]
	23	hi. Dillencourt, D. Mount, and N. Netanyahu. A randomized algorithm for slope selection. Int. A Comput. Geom. Appl., 2:1-27, 1992.
	24	Z. Drezner. On the rectangular p-center problem. Naval Res. i.ogist. Quart., 34:229-234, 1987.
	25	hi. E. Dyer. Linear time algorithms for two- and threevariable lhte# programs. SIAM J. Comput., 13:31-45, 1954.
	26	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]
	27	David Eppstein, Faster construction of planar two-centers, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.131-138, January 05-07, 1997, New Orleans, Louisiana, United States
	28	D. Eppstein and J. Erickson. Iterated nearest neighbors and finding mlnlrnal polytopes. Discrete Comput. G,.om., 11:321-350, 1994.
	29	H. Everett., .}.-hi. Robert, and M. van Kreveld. An optimal algorithm for the (<: k)-levels, with applications to zepztration and transversal problems, int. J. Uomput. Geom. Appl., 6:247-261, 1996.
	30	G. N. Frederickson and D. B. Johnson. The comple#Sty of selection and ranldng in X + Y and matrices with zorted rows and columns. J. Comput. Sys. Sci., 24:197- 203, 1982.
	31	F. Gao, L. J. Guibas, D. G. Kirkpatrick, W. T. Laaser, and J. Sane. Finding extrema with unary predicates. Algorithmica, 9:591-600, 1993.
	32	Alex Glozman , Klara Kedem , Gregory Shpitalnik, On Some Geometric Selection and Optimization Problems via Sorted Matrices, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.26-37, August 16-18, 1995
	33	Sariel Har-Peled, Constructing cuttings in theory and practice, Proceedings of the fourteenth annual symposium on Computational geometry, p.327-336, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276921]
	34	D. P. Huttenlocher, K. Kedem, and M. Sharir. The upper envelope of Voronoi surfaces and its applications. D#screte Comput. Geom., 9:267-291, 1993.
	35	Matthew J. Katz , Micha Sharir, An Expander-Based Approach to Geometric Optimization, SIAM Journal on Computing, v.26 n.5, p.1384-1408, Oct. 1997 [doi>10.1137/S0097539794268649]
	36	D. E. Knuth. Fundamental Algorithms, volume 1 of The Art of Computer Programming. Addison-W(vley, 1968.
	37	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]
	38	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	39	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]
	40	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]
	41	J. Matou#ek. On geometric optimization with few violated constraints. Discrete Gomput. Geom., 1,t:365- 384# 1995.
	42	J. Matou#ek. On constants for cuttings in the plane. Discrete Comput. Geom., to appear.
	43	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Computational Geometry: Theory and Applications, v.6 n.4, p.253-262, July 1996 [doi>10.1016/0925-7721(95)00025-9]
	44	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]
	45	N. Megiddo. Linear time "algorithms for linear programming in/g3 and related problems. SIAM J. Comput., 12:759-776, 1983.
	46	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]
	47	M. O. Rabin. ProbabiUstic algorithms. In Algorithms and Complexity (J. F. Traub, ed.), pages 21--30, Academic Press, New York, NY, 1976.
	48	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France [doi>10.1145/262839.262864]
	49	Thomas Roos , Peter Widmayer, k-Violation linear programming, Information Processing Letters, v.52 n.2, p.109-114, Oct. 28, 1994 [doi>10.1016/0020-0190(94)00134-0]
	50	Michael Segal, On Piercing Sets of Axis-Parallel Rectangles and Rings, Proceedings of the 5th Annual European Symposium on Algorithms, p.430-442, September 15-17, 1997
	51	M. Shark. A near-lineax algorithm for the planar 2- center problem. Discrete Comput. Geom., 18:125--134# 1997.
	52	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
	53	Micha Sharir , Emo Welzl, Rectilinear and polygonal p-piercing and p-center problems, Proceedings of the twelfth annual symposium on Computational geometry, p.122-132, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237255]

CITED BY 5

	David Eppstein , Jeff Erickson, Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions, Proceedings of the fourteenth annual symposium on Computational geometry, p.58-67, June 07-10, 1998, Minneapolis, Minnesota, 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
	Pankaj K. Agarwal , Boris Aronov , Sariel Har-Peled , Micha Sharir, Approximation and exact algorithms for minimum-width annuli and shells, Proceedings of the fifteenth annual symposium on Computational geometry, p.380-389, June 13-16, 1999, Miami Beach, Florida, United States
	Pat Morin, An optimal randomized algorithm for d-variate zonoid depth, Computational Geometry: Theory and Applications, v.39 n.3, p.229-235, April, 2008
	Jean Cardinal , Sébastien Collette , Ferran Hurtado , Stefan Langerman , Belén Palop, Optimal location of transportation devices, Computational Geometry: Theory and Applications, v.41 n.3, p.219-229, November, 2008