We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric searching, geometric alternatives to parametric searching, prune-and-search techniques for linear programming and related problems, and LP-type problems and their efficient solution. We then describe a wide range of applications of these and other techniques to numerous problems in geometric optimization, including facility location, proximity problems, statistical estimators and metrology, placement and intersection of polygons and polyhedra, and ray shooting and other query-type problems.

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 , Pavan K. Desikan, An efficient algorithm for terrain simplification, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.139-147, January 05-07, 1997, New Orleans, Louisiana, United States
	2	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]
	3	AGARWAL, P. K. AND MATOUSEK, J. 1994. On range searching with semialgebraic sets. Discrete Comput. Geom. 11,393-418.
	4	AGARWAL, P. K. AND MATOUSEK, J. 1995. Dynamic half-space range reporting and its applications. Algorithmica 13, 325-345.
	5	Pankaj K. Agarwal , Cecilia M. Procopiuc, Exact and approximation algorithms for clustering, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.658-667, January 25-27, 1998, San Francisco, California, United States
	6	Pankaj K. Agarwal , Micha Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications, v.1 n.2, p.65-78, Sept. 1991  [doi>10.1016/S0925-7721(00)00026-2 ]
	7	AGARWAL, P. K. AND SHARIR, M. 1994. Planar geometric location problems. Algorithmica 11, 185-195.
	8	AGARWAL, P. K. AND SHARIR, M. 1996a. Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom. 16, 317-337.
	9	Pankaj K. Agarwal , Micha Sharir, Ray shooting amidst convex polygons in 2D, Journal of Algorithms, v.21 n.3, p.508-519, Nov. 1996  [doi>10.1006/jagm.1996.0056 ]
	10	Pankaj K. Agarwal , Micha Sharir, Ray Shooting Amidst Convex Polyhedra and PolyhedralTerrains in Three Dimensions, SIAM Journal on Computing, v.25 n.1, p.100-116, Feb. 1996  [doi>10.1137/S0097539793244368]
	11	Pankaj K. Agarwal , Subhash Suri, Surface approximation and geometric partitions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.24-33, January 23-25, 1994, Arlington, Virginia, United States
	12	AGARWAL, P. K., AMENTA, N., AND SHARIR, M. 1998. Placement of one convex polygon inside another. Discrete Comput. Geom. 19, 95-104.
	13	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing Envelopes in Four Dimensions with Applications, SIAM Journal on Computing, v.26 n.6, p.1714-1732, Dec. 1997  [doi>10.1137/S0097539794265724]
	14	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Line transversals of balls and smallest enclosing cylinders in three dimensions, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.483-492, January 05-07, 1997, New Orleans, Louisiana, United States
	15	AGARWAL, P. K., ARONOV, B., AND SHARIR, M. 1997c. Motion planning for a convex polygon in a polygonal environment. Tech. Rep. CS-1997-17, Dept. of Computer Science, Duke University.
	16	AGARWAL, P. K., ARONOV, B., SHARIR, M., AND SURI, S. 1993a. Selecting distances in the plane. Algorithmica 9, 495-514.
	17	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]
	18	Pankaj K. Agarwal , Alon Efrat , Micha Sharir , Sivan Toledo, Computing a segment center for a planar point set, Journal of Algorithms, v.15 n.2, p.314-323, Sept. 1993  [doi>10.1006/jagm.1993.1043 ]
	19	K P Agarwal , Micha Sharir , Sivan Toledo, An Efficient Multi-Dimensional Searching Technique and itsApplications, Duke University, Durham, NC, 1993
	20	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Journal of Algorithms, v.17 n.3, p.292-318, Nov. 1994
	21	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]
	22	Richa Agarwala , David Fernandez-Baca, Weighted Multidimensional Search and itsApplication to Convex Optimization, SIAM Journal on Computing, v.25 n.1, p.83-99, Feb. 1996  [doi>10.1137/S0097539792241928]
	23	Alok Aggarwal , Maria Klawe, Applications of generalized matrix searching to geometric algorithms, Discrete Applied Mathematics, v.27 n.1-2, p.3-23, May 1990  [doi>10.1016/0166-218X(90)90124-U ]
	24	AGGARWAL, A. AND PARK, J. K. 1988. Notes on searching in multidimensional monotone arrays. In Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science, 497-512.
	25	AGGARWAL, A., KLAWE, M. M., MORAN, S., SHOR, P. W., AND WILBER, R. 1987. Geometric applications of a matrix-searching algorithm. Algorithmica 2, 195-208.
	26	A. Aggarwal , D. Kravets , J. Park , S. Sen, Parallel searching in generalized Monge arrays with applications, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.259-268, July 02-06, 1990, Island of Crete, Greece  [doi>10.1145/97444.97693]
	27	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
	28	Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
	29	Miklos Ajtai , Nimrod Megiddo, A Deterministic poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension, SIAM Journal on Computing, v.25 n.6, p.1171-1195, Dec. 1996  [doi>10.1137/S0097539792234858]
	30	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983  [doi>10.1007/BF02579338]
	31	ALON, N. AND MEGIDDO, N. 1990. Parallel linear programming in fixed dimension almost surely in constant time. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, 574-582.
	32	ALON, N. AND SPENCER, J. 1993. The Probabilistic Method. Wiley, New York.
	33	ALT, H., BEHRENDS, B., AND BL(~MER, J. 1995. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell. 13, 251-266.
	34	AMATO, N. M., GOODRICH, M. T., AND RAMOS, E.A. 1994. Parallel algorithms for higherdimensional convex hulls. In Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, 683-694.
	35	Nina Amenta, Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem, Proceedings of the tenth annual symposium on Computational geometry, p.340-347, June 06-08, 1994, Stony Brook, New York, United States  [doi>10.1145/177424.178064]
	36	AMENTA, N. 1994b. Helly-type theorems and generalized linear programming. Discrete Comput. Geom. 12, 241-261.
	37	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984  [doi>10.1137/0213054]
	38	S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
	39	S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.554, October 19-22, 1997
	40	Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States  [doi>10.1145/276698.276718]
	41	Judit Bar-Ilan , Guy Kortsarz , David Peleg, How to allocate network centers, Journal of Algorithms, v.15 n.3, p.385-415, Nov. 1993  [doi>10.1006/jagm.1993.1047 ]
	42	BAR-YEHUDA, R., EFRAT, A., AND ITAI, A. 1993. A simple algorithm for maintaining the center of a planar point-set. In Proceedings of the Fifth Canadian Conference on Computational Geometry, 252-257.
	43	Mark Berman, Large sample bias in least squares estimators of a circular arc center and its radius, Computer Vision, Graphics, and Image Processing, v.45 n.1, p.126-128, January 1989  [doi>10.1016/0734-189X(89)90075-3]
	44	Marshall Bern , David Eppstein, Approximation algorithms for geometric problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	45	Sergei N. Bespamyatnikh, An efficient algorithm for the three-dimensional diameter problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 25-27, 1998, San Francisco, California, United States
	46	Binay Bhattacharya , G. Toussaint, Computing shortest transversals, Computing, v.46 n.2, p.93-119, 1991  [doi>10.1007/BF02239165]
	47	Binay Bhattacharya , Jurek Czyzowicz , Peter Egyed , Ivan Stojmenovic , Godfried Toussaint , Jorge Urrutia, Computing shortest transversals of sets (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.71-80, June 10-12, 1991, North Conway, New Hampshire, United States  [doi>10.1145/109648.109656]
	48	Binay K. Bhattacharya , Sreesh Jadhav , Asish Mukhopadhayay , Jean-Marc Robert, Optimal algorithms for some smallest intersection radius problems (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.81-88, June 10-12, 1991, North Conway, New Hampshire, United States  [doi>10.1145/109648.109657]
	49	Thomas Brinkhoff , Hans-Peter Kriegel, The Impact of Global Clustering on Spatial Database Systems, Proceedings of the 20th International Conference on Very Large Data Bases, p.168-179, September 12-15, 1994
	50	BRONNIMANN, H. AND CHAZELLE, B. 1994. Optimal slope selection via cuttings. In Proceedings of the Sixth Canadian Conference on Computational Geometry, 99-103.
	51	BRONNIMANN, H. AND GOODRICH, M. T. 1995. Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 263-279.
	52	BRONNIMANN, H., CHAZELLE, B., AND MATOUSEK, J. 1993. Product range spaces, sensitive sampling, and derandomization. In Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science, 400- 409.
	53	Fazli Can, Incremental clustering for dynamic information processing, ACM Transactions on Information Systems (TOIS), v.11 n.2, p.143-164, April 1993  [doi>10.1145/130226.134466]
	54	CANNY, J. AND REIF, J. H. 1987. New lower bound techniques for robot motion planning problems. In Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, 49-60.
	55	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]
	56	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  [doi>10.1145/276884.276915]
	57	R. Chandrasekaran , A. Tamir, Algebraic optimization: the Fermat-Weber location problem, Mathematical Programming: Series A and B, v.46 n.2, p.219-224, Feb. 1990
	58	Moses Charikar , Chandra Chekuri , Tomás Feder , Rajeev Motwani, Incremental clustering and dynamic information retrieval, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.626-635, May 04-06, 1997, El Paso, Texas, United States  [doi>10.1145/258533.258657]
	59	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993
	60	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 ]
	61	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991  [doi>10.1016/0304-3975(91)90261-Y ]
	62	CHAZELLE, B., EDELSBRUNNER, H., GUIBAS, L. J., AND SHARIR, M. 1993. Diameter, width, closest line pair and parametric searching. Discrete Comput. Geom. 10, 183-196.
	63	CHAZELLE, B., EDELSBRUNNER, H., GUIBAS, L. J., AND SHARIR, M. 1994. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica 11, 116-132.
	64	CHAZELLE, B., EDELSBRUNNER, H., GUIBAS, L. J., SHARIR, M., AND STOLFI, J. 1996. Lines in space: Combinatorics and algorithms. Algorithmica 15, 428-447.
	65	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
	66	L. Paul Chew , Klara Kedem, A convex polygon among polygonal obstacles: placement and high-clearance motion, Computational Geometry: Theory and Applications, v.3 n.2, p.59-89, July 1993  [doi>10.1016/0925-7721(93)90001-M ]
	67	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
	68	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 ]
	69	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]
	70	CLARKSON, K. L. 1992. Randomized geometric algorithms. In Computing in Euclidean Geometry, D.-Z. Du and F. K. Hwang, Eds., World Scientific, Singapore, 117-162.
	71	Kenneth L. Clarkson, Algorithms for Polytope Covering and Approximation, Proceedings of the Third Workshop on Algorithms and Data Structures, p.246-252, August 11-13, 1993
	72	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]
	73	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
	74	CLARKSON, K. L., EPPSTEIN, D., MILLER, G. L., STURTIVANT, C., AND TENG, S.-H. 1996. Approximating center points with iterative Radon points. Int. J. Comput. Geom. Appl. 6, 357-377.
	75	COHEN, E. AND MEGIDDO, N. 1993. Maximizing concave functions in fixed dimension. In Complexity in Numeric Computation (P. Pardalos, Ed., World Scientific, Singapore, 74-87.
	76	Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996  [doi>10.1145/237170.237220]
	77	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]
	78	Richard Cole , Jeffrey S. Salowe , W. L. Steiger , Endre Szemerédi, An optimal-time algorithm for slope selection, SIAM Journal on Computing, v.18 n.4, p.792-810, Aug. 1989  [doi>10.1137/0218055]
	79	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]
	80	George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
	81	Douglass R. Cutting , David R. Karger , Jan O. Pedersen, Constant interaction-time scatter/gather browsing of very large document collections, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.126-134, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States  [doi>10.1145/160688.160706]
	82	Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark  [doi>10.1145/133160.133214]
	83	DANZER, L., GRfJNBAUM, B., AND KLEE, V. 1963. Helly's theorem and its relatives. In Convexity, Proceedings of the Symposium on Pure Mathematics, Vol. 7, American Mathematical Society, Providence, RI 101-180.
	84	DAS, G. AND JOSEPH, D. 1990. The complexity of minimum convex nested polyhedra. In Proceedings of the Second Canadian Conference on Computational Geometry, 296-301.
	85	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 ]
	86	Mark de Berg , Prosenjit Bose , David Bremner , Suneeta Ramaswami , Gordon T. Wilfong, Computing Constrained Minimum-Width Annuli of Point Sets, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.392-401, August 06-08, 1997
	87	Mark de Berg , Olivier Devillers , Marc J. van Kreveld , Otfried Schwarzkopf , Monique Teillaud, Computing the Maximum Overlap of Two Convex Polygons Under Translations, Proceedings of the 7th International Symposium on Algorithms and Computation, p.126-135, December 16-18, 1996
	88	L. De Floriani, A graph based approach to object feature recognition, Proceedings of the third annual symposium on Computational geometry, p.100-109, June 08-10, 1987, Waterloo, Ontario, Canada  [doi>10.1145/41958.41968]
	89	DEHAEMER, M. J., JR. AND ZYDA, M. J. 1991. Simplification of objects rendered by polygonal approximations. Comput. Graph. 15, 175- 184.
	90	X. Deng, An optimal parallel algorithm for linear programming in the plane, Information Processing Letters, v.35 n.4, p.213-217, Aug. 1990  [doi>10.1016/0020-0190(90)90026-T ]
	91	DILLENCOURT, M. B., MOUNT, D. M., AND NETAN- YAHU, N.S. 1992. A randomized algorithm for slope selection. Int. J. Comput. Geom. Appl. 2, 1-27.
	92	DREZNER, Z. 1981. On a modified l-center problem. Manage Sci. 27, 838-851.
	93	DREZNER, Z. 1984a. The p-centre problems- Heuristic and optimal algorithms. J. Oper. Res. Soc. 35, 741-748.
	94	DREZNER, Z. 1984b. The planar two-center and two-median problem. Transp. Sci. 18, 351- 361.
	95	DREZNER, Z. 1987. On the rectangular p-center problem. Naval Res. Logist. Q. 34, 229-234.
	96	DREZNER, Z. 1989. Conditional p-centre problems. Transp. Sci. 23, 51-53.
	97	DREZNER, Z., ED. 1995. Facility Location. Springer-Verlag, New York.
	98	DREZNER, Z., MEHREZ, n., AND WESOLOWSKY, G.O. 1992. The facility location problems with limited distances. Transp. Sci. 25, 183- 187.
	99	Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
	100	DYER, M. E. 1984. Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput. 13, 31-45.
	101	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]
	102	Martin Dyer, A class of convex programs with applications to computational geometry, Proceedings of the eighth annual symposium on Computational geometry, p.9-15, June 10-12, 1992, Berlin, Germany  [doi>10.1145/142675.142681]
	103	Martin Dyer, A parallel algorithm for linear programming in fixed dimension, Proceedings of the eleventh annual symposium on Computational geometry, p.345-349, June 05-07, 1995, Vancouver, British Columbia, Canada  [doi>10.1145/220279.220316]
	104	DYER, M. E. AND FRIEZE, A. M. 1985. A simple heuristic for the p-centre problem. Oper. Res. Lett. 3, 285-288.
	105	M. E. Dyer , A. M. Frieze, A randomized algorithm for fixed-dimensional linear programming, Mathematical Programming: Series A and B, v.44 n.2, p.203-212, 1989
	106	EBARA, H., FUKUYAMA, N., NAKANO, H., AND NA- KANISHI, Y. 1980. Roundness algorithms using the Voronoi diagrams. In Abstracts of the First Canadian Conference on Computational Geometry, 41.
	107	ECKHOFF, J. 1993. Helly, Radon, and Carath- ~odory type theorems. In Handbook of Convex Geometry, P. M. Gruber and J. Wills, Eds., North-Holland, 389-448.
	108	H. Edelsbrunner, Computing the extreme distances between two convex polygons, Journal of Algorithms, v.6 n.2, p.213-224, June 1985  [doi>10.1016/0196-6774(85)90039-2]
	109	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	110	H. Edelsbrunner , R. Waupotitsch, Computing a ham-sandwich cut in two dimensions, Journal of Symbolic Computation, v.2 n.2, p.171-178, June 1986  [doi>10.1006/jsco.1998.0247 ]
	111	EFRAT, A. AND SHARIR, M. 1996. A near-linear algorithm for the planar segment center problem. Discrete Comput. Geom. 16, 239-257.
	112	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 ]
	113	Mark J. Eisner , Dennis G. Severance, Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases, Journal of the ACM (JACM), v.23 n.4, p.619-635, Oct. 1976  [doi>10.1145/321978.321982]
	114	EPPSTEIN, D. 1992. Dynamic three-dimensional linear programming. ORSA J. Comput. 4, 360 -368.
	115	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
	116	David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
	117	EPPSTEIN, D. AND ERICKSON, g. 1994. Iterated nearest neighbors and finding minimal polytopes. Discrete Comput. Geom. 11,321-350.
	118	W. Eric L. Grimson, Object recognition by computer: the role of geometric constraints, MIT Press, Cambridge, MA, 1991
	119	Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62255]
	120	P. W. Finn , L. E. Kavraki , J.-C. Latombe , R. Motwani , C. Shelton , S. Venkatasubramanian , A. Yao, RAPID: randomized pharmacophore identification for drug design, Proceedings of the thirteenth annual symposium on Computational geometry, p.324-333, June 04-06, 1997, Nice, France  [doi>10.1145/262839.262993]
	121	James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	122	FOLLERT, F., SCHOMER, E., AND SELLEN, J. 1995. Subquadratic algorithms for the weighted maximum facility location problem. In Proceedings of the Seventh Canadian Conference on Computational Geometry, 1-6.
	123	Frank Follert , Elmar Schömer , Jürgen Sellen , Michiel H. M. Smid , Christian Thiel, Computing a Largest Empty Anchored Cylinder, and Related Problems, Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science, p.428-442, December 18-20, 1995
	124	FOWLER, R. J., PATERSON, M. S., AND TANIMOTO, S.L. 1981. Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12, 133-137.
	125	Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
	126	FREDERICKSON, G. N. AND JOHNSON, D. B. 1982. The complexity of selection and ranking in X + Y and matrices with sorted rows and columns. J. Comput. Syst. Sci. 24, 197-208.
	127	FREDERICKSON, G. N. AND JOHNSON, D. B. 1983. Finding kth paths and p-centers by generating and searching good data structures. J. Alg. 4, 61-80.
	128	FREDERICKSON, G. N. AND JOHNSON, D. B. 1984. Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13, 14-30.
	129	Jesús García-López , Pedro A. Ramos, Fitting a set of points by a circle, Proceedings of the thirteenth annual symposium on Computational geometry, p.139-146, June 04-06, 1997, Nice, France  [doi>10.1145/262839.262919]
	130	Bernd Gartner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, v.24 n.5, p.1018-1035, Oct. 1995  [doi>10.1137/S0097539793250287]
	131	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
	132	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
	133	Michael Goldwasser, A survey of linear programming in randomized subexponential time, ACM SIGACT News, v.26 n.2, p.96-104, June 1995  [doi>10.1145/202840.202847]
	134	GONZALEZ, T. 1985. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293-306.
	135	GONZALEZ, T. 1991. Covering a set of points in multidimensional space. Inf. Process. Lett. 40, 181-188.
	136	Michael T. Goodrich, Geometric partitioning made easier, even in parallel, Proceedings of the ninth annual symposium on Computational geometry, p.73-82, May 18-21, 1993, San Diego, California, United States  [doi>10.1145/160985.161002]
	137	GOODRICH, M. T. 1995. Efficient piecewise-linear function approximation using the uniform metric. Discrete Comput. Geom. 14, 445-462.
	138	GOODRICH, M. T. AND RAMOS, E. A. 1997. Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming. Discrete Comput. Geom. 18, 397-420.
	139	Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.103-112, June 06-08, 1994, Stony Brook, New York, United States  [doi>10.1145/177424.177572]
	140	GRfJNBAUM, B. 1956. A proof of V~zsonyi's conjecture. Bull. Res. Council Isr., Sect. A, 6, 77-78.
	141	GUPTA, P., JANARDAN, R., AND SMID, M. 1994. Fast algorithms for collision and proximity problems involving moving geometric objects. Rep. MPI-I-94-113, Max-Planck-Institut Inform., Saarbrficken, Germany.
	142	GUSFIELD, D., BALASUBRAMANIAN, K., AND NAOR, D. 1994. Parametric optimization of sequence alignment. Algorithmica 12, 312-326.
	143	Kyung-Ah Han , Sung-Hyun Myaeng, Image organization and retrieval with automatically constructed feature vectors, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.157-165, August 18-22, 1996, Zurich, Switzerland  [doi>10.1145/243199.243256]
	144	Refael Hassin , Nimrod Megiddo, Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics, v.30 n.1, p.29-42, Jan. 7, 1991  [doi>10.1016/0166-218X(91)90011-K ]
	145	HECKBERT, P. S. AND GARLAND, M. 1995. Fast polygonal approximation of terrains and height fields. Tech. Rep. CMU-CS-95-181, Carnegie Mellon University.
	146	HELLY, E. 1930. Uber Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten. Monaths. Math. und Physik 37, 281-302.
	147	HEPPES, A. 1956. Beweis einer Vermutung von A. V~zonyi. Acta Math. Acad. Sci. Hungar. 7, 463-466.
	148	John Hershberger, Minimizing the sum of diameters efficiently, Computational Geometry: Theory and Applications, v.2 n.2, p.111-118, Oct. 1992  [doi>10.1016/0925-7721(92)90028-Q ]
	149	John Hershberger, A faster algorithm for the two-center decision problem, Information Processing Letters, v.47 n.1, p.23-29, Aug. 9, 1993  [doi>10.1016/0020-0190(93)90153-Z ]
	150	John Hershberger , Subhash Suri, Finding tailored partitions, Journal of Algorithms, v.12 n.3, p.431-463, Sept. 1991  [doi>10.1016/0196-6774(91)90013-O]
	151	HERSHBERGER, J. AND SURI, S. 1993a. Efficient computation of Euclidean shortest paths in the plane. In Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science, 508-517.
	152	John Hershberger , Subhash Suri, Matrix searching with the shortest path metric, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.485-494, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167220]
	153	Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985  [doi>10.1145/2455.214106]
	154	Dorit S. Hochbaum , Wolfgang Maass, Fast approximation algorithms for a nonconvex covering problem, Journal of Algorithms, v.8 n.5, p.305-323, Sept. 1987
	155	HOCHBAUM, D. S. AND SHMOYS, D. 1985. A best possible heuristic for the k-center problem. Math. Oper. Res. 10, 180-184.
	156	Dorit S. Hochbaum , David B. Shmoys, A unified approach to approximation algorithms for bottleneck problems, Journal of the ACM (JACM), v.33 n.3, p.533-550, July 1986  [doi>10.1145/5925.5933]
	157	HOCKEN, R. J., RAJA, J., AND BABU, U. 1993. Sampling issues in coordinate metrology. Man. Rev. 6, 282-294.
	158	Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997  [doi>10.1145/258734.258843]
	159	Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994  [doi>10.1145/192161.192233]
	160	Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993  [doi>10.1145/166117.166119]
	161	M. E. Houle , G. T. Toussaint, Computing the Width of a Set, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.761-765, September 1988  [doi>10.1109/34.6790 ]
	162	Michael E. Houle , Hiroshi Imai , Keiko Imai , Jean-Marc Robert, Weighted Orthogonal Linear L\infty-Approximation and Applications, Proceedings of the Workshop on Algorithms and Data Structures, p.183-193, August 17-19, 1989
	163	Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States  [doi>10.1145/98524.98599]
	164	HUTTENLOCHER, D. P., KEDEM, K., AND SHARIR, M. 1993. The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom. 9, 267-291.
	165	D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993  [doi>10.1109/34.232073 ]
	166	HWANG, R. Z., CHANG, R. C., AND LEE, R. C.T. 1993a. The generalized searching over separators strategy to solve some NP- hard problems in subexponential time. Algorithmica 9, 398-423.
	167	HWANG, R. Z., LEE, R. C. T., AND CHANG, R.C. 1993b. The slab dividing approach to solve the Euclidean p-center problem. Algorithmica 9, 1-22.
	168	IMAI, H., LEE, D., AND YANG, C. 1992. l-segment center covering problems. ORSA J. Comput. 4, 426-434.
	169	JADHAV, S. AND MUKHOPADHYAY, A. 1994. Computing a centerpoint of a finite planar set of points in linear time. Discrete Comput. Geom. 12, 291-312.
	170	Shreesh Jadhav , Asish Mukhopadhyay , Binay Bhattacharya, An optimal algorithm for the intersection radius of a set of convex polygons, Journal of Algorithms, v.20 n.2, p.244-267, March 1996  [doi>10.1006/jagm.1996.0013 ]
	171	Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	172	Jerzy W. Jaromczyk , Mirosław Kowaluk, An efficient algorithm for the Euclidean two-center problem, Proceedings of the tenth annual symposium on Computational geometry, p.303-311, June 06-08, 1994, Stony Brook, New York, United States  [doi>10.1145/177424.178038]
	173	JAROMCZYK, J. W. AND KOWALUK, M. 1995a. A geometric proof of the combinatorial bounds for the number of optimal solutions to the 2-center Euclidean problem. In Proceedings of the Seventh Canadian Conference on Computational Geometry, 19-24.
	174	Jerzy W. Jaromczyk , Miroslaw Kowaluk, The Two-Line Center Problem from a Polar View: A New Algorithm and Data Structure, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.13-25, August 16-18, 1995
	175	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]
	176	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984  [doi>10.1007/BF02579150]
	177	Improved algorith