Efficient algorithms for geometric optimization

ABSTRACT

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.

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 [doi>10.1007/BF01585739]
• 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 [doi>10.1007/BF02189314]
• 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 [doi>10.1007/BF02187740]
• 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 [doi>10.1007/BF01587088]
• 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 [doi>10.1016/0196-6774(87)90012-5]
• 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 algorithms in geometric optimization via expanders, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.78, January 04-06, 1995
• 178: Matthew J. Katz , Franck Nielsen, On piercing sets of objects, Proceedings of the twelfth annual symposium on Computational geometry, p.113-121, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237253]
• 179: Matthew J. Katz , Micha Sharir, Optimal slope selection via expanders, Information Processing Letters, v.47 n.3, p.115-122, Sept. 14, 1993 [doi>10.1016/0020-0190(93)90234-Z]
• 180: 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]
• 181: KAUFMAN, L. AND ROUSSEEUW, P.J. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York.
• 182: KHACHIYAN, L. G. 1980. Polynomial algorithm in linear programming. U.S.S.R. Comput. Math. Math. Phys. 20, 53-72.
• 183: Samir Khuller , Yoram J. Sussmann, The Capacitated K-Center Problem (Extended Abstract), Proceedings of the Fourth Annual European Symposium on Algorithms, p.152-166, September 25-27, 1996
• 184: KNUTH, D.E. 1973. Sorting and Searching. Addison-Wesley, Reading, MA.
• 185: M. T. Ko , Y. T. Ching, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under l∞ -distance, Discrete Applied Mathematics, v.40 n.3, p.397-410, Dec. 14, 1992 [doi>10.1016/0166-218X(92)90009-Y]
• 186: M. T. Ko , R. C. T. Lee, On weighted rectilinear 2-center and 3-center problems, Information Sciences: an International Journal, v.54 n.1-2, p.169-190, March 1991 [doi>10.1016/0020-0255(91)90050-5]
• 187: Ko, M. T., LEE, R. C. T., AND CHANG, J.S. 1990. An optimal approximation algorithm for the rectilinear m-center problem. Algorithmica 5, 341-352.
• 188: KORNEENKO, N. M. AND MARTINI, H. 1993. Hyperplane approximation and related topics. In New Trends in Discrete and Computational Geometry, J. Pach, Ed., Algorithms and Combinatorics, Springer-Verlag, Heidelberg, 135- 161.
• 189: U M Landau, Estimation of a circular arc center and its radius, Computer Vision, Graphics, and Image Processing, v.38 n.3, p.317-326, June 1987 [doi>10.1016/0734-189X(87)90116-2]
• 190: Van-Ban Le , D. T. Lee, Out-of-Roundness Problem Revisited, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.3, p.217-223, March 1991 [doi>10.1109/34.75510]
• 191: LEE, D. T. AND WU, Y.F. 1986. Geometric complexity of some location problems. Algorithmica 1, 193-211.
• 192: LEVEN, D. AND SHARIR, M. 1987. On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space. Discrete Comput. Geom. 2, 255-270.
• 193: Lo, C.-Y. AND STEIGER, W. 1990. An optimaltime algorithm for ham-sandwich cuts in the plane. In Proceedings of the Second Canadian Conference on Computational Geometry, 5-9.
• 194: Lo, C.-Y., MATOUSEK, J., AND STEIGER, W.L. 1994. Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11,433-452.
• 195: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 196: Wolfgang Maass, On the complexity of nonconvex covering, SIAM Journal on Computing, v.15 n.2, p.453-467, May 1986 [doi>10.1137/0215031]
• 197: Paola Magillo , Leila De Floriani, Maintaining Multiple Levels of Detail in the Overlay of Hierarchical Sub Divisions, Proceedings of the 8th Canadian Conference on Computational Geometry, p.190-195, August 12-15, 1996
• 198: MAKHOUL, J., ROUCOS, S., AND GISH, H. 1985. Vector quantization in speech coding. In Proceedings of the IEEE 73, 1551-1588.
• 199: MATOUSEK, J. 1991a. Computing the center of planar point sets. In Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman, R. Pollack, and W. Steiger, Eds., American Mathematical Society, Providence, 221-230.
• 200: 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]
• 201: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 202: Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
• 203: MATOUSEK, J. 1994. Lower bound for a subexponential optimization algorithm. Random Struct. Alg. 5, 591-607.
• 204: 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]
• 205: MATOUSEK, J. 1995b. On geometric optimization with few violated constraints. Discrete Comput. Geom. 14, 365-384.
• 206: 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]
• 207: Jiří Matoušek , David M. Mount , Nathan S. Netanyahu, Efficient randomized algorithms for the repeated median line estimator, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.74-82, January 25-27, 1993, Austin, Texas, United States
• 208: MATOUSEK, J., SHARIR, M., AND WELZL, E. 1996. A subexponential bound for linear programming. Algorithmica 16, 498-516.
• 209: Carlo Meghini, An image retrieval model based on classical logic, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.300-308, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215375]
• 210: MEGIDDO, N. 1979. Combinatorial optimization with rational objective functions. Math. Oper. Res. 4, 414-424.
• 211: 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]
• 212: MEGIDDO, N. 1983b. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12, 759-776.
• 213: MEGIDDO, N. 1983c. The weighted Euclidean l-center problem. Math. Oper. Res. 8, 498- 504.
• 214: 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]
• 215: MEGIDDO, N. 1985. Partitioning with two lines in the plane. J. Alg. 6, 430-433.
• 216: N. Megiddo, On the ball spanned by balls, Discrete & Computational Geometry, v.4 n.6, p.605-610, Sep. 1989 [doi>10.1007/BF02187750]
• 217: N. Megiddo, On the complexity of some geometric problems in unbounded dimension, Journal of Symbolic Computation, v.10 n.3-4, p.327-334, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80067-3]
• 218: MEGIDDO, N. AND SUPOWIT, K.J. 1984. On the complexity of some common geometric location problems. SIAM J. Comput. 13, 182-196.
• 219: MEGIDDO, N. AND TAMIR, A. 1982. On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1, 194-197.
• 220: MEGIDDO, N. AND ZEMEL, E. 1986. A randomized O(n log n) algorithm for the weighted Euclidean l-center problem. J. Alg. 7, 358- 368.
• 221: Kurt Mehlhorn , Thomas C. Shermer , Chee K. Yap, A complete roundness classification procedure, Proceedings of the thirteenth annual symposium on Computational geometry, p.129-138, June 04-06, 1997, Nice, France [doi>10.1145/262839.262917]
• 222: Joseph S. B. Mitchell, Shortest paths among obstacles in the plane, Proceedings of the ninth annual symposium on Computational geometry, p.308-317, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161156]
• 223: MITCHELL, J. S. B. 1996. Shortest paths and networks. Tech. Rep., University at Stony Brook.
• 224: Joseph S. B. Mitchell , Subhash Suri, Separation and approximation of polyhedral objects, Computational Geometry: Theory and Applications, v.5 n.2, p.95-114, Sept. 1995 [doi>10.1016/0925-7721(95)00006-U]
• 225: Joseph S. B. Mitchell , David M. Mount , Subhash Suri, Query-sensitive ray shooting, Proceedings of the tenth annual symposium on Computational geometry, p.359-368, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178094]
• 226: Shai Mohaban , Micha Sharir, Ray Shooting Amidst Spheres in Three Dimensions and Related Problems, SIAM Journal on Computing, v.26 n.3, p.654-674, June 1997 [doi>10.1137/S0097539793252080]
• 227: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 228: MULMULEY, Z. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, NJ.
• 229: NAOR, N. AND SHARIR, M. 1990. Computing a point in the center of a point set in three dimensions. In Proceedings of the Second Canadian Conference on Computational Geometry, 10-13.
• 230: Carolyn Haibt Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Journal of Algorithms, v.13 n.1, p.79-98, March 1992 [doi>10.1016/0196-6774(92)90006-X]
• 231: PAPADIMITRIOU, C. H. 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM J. Comput. 10, 542-557.
• 232: PELLEGRINI, M. 1993. Ray shooting on triangles in 3-space. Algorithmica 9, 471-494.
• 233: Marco Pellegrini, On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space, SIAM Journal on Computing, v.23 n.1, p.133-153, Feb. 1994 [doi>10.1137/S0097539792229404]
• 234: Marco Pellegrini, Repetitive hidden surface removal for polyhedra, Journal of Algorithms, v.21 n.1, p.80-101, July 1996 [doi>10.1006/jagm.1996.0038]
• 235: J. Plesnik, A heuristic for the p-center problem in graphs, Discrete Applied Mathematics, v.17 n.3, p.263-268, June 1987 [doi>10.1016/0166-218X(87)90029-1]
• 236: Mark J. Post, Minimum spanning ellipsoids, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.108-116, December 1984 [doi>10.1145/800057.808672]
• 237: 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]
• 238: Edgar A. Ramos, Intersection of unit-balls and diameter of point set in R³ , Computational Geometry: Theory and Applications, v.8 n.2, p.57-65, July 1997 [doi>10.1016/S0925-7721(96)00010-7]
• 239: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 240: M. Reichling, On the detection of a common intersection of k convex objects in the plane, Information Processing Letters, v.29 n.1, p.25-29, Sept. 15, 1988 [doi>10.1016/0020-0190(88)90127-5]
• 241: M. Reichling, On the detection of a common intersection of k convex polyhedra, Proceedings on International Workshop on Computational Geometry on Computational Geometry and its Applications, p.180-186, October 1988, Wu:9Airzburg, Germany
• 242: John H. Reif , James A. Storer, A single-exponential upper bound for finding shortest paths in three dimensions, Journal of the ACM (JACM), v.41 n.5, p.1013-1019, Sept. 1994 [doi>10.1145/185675.185811]
• 243: 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]
• 244: RoY, U. AND ZHANG, X. 1992. Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error. Comput. Aided Des. 24, 161-168.
• 245: Jeffrey S. Salowe, L-infinity interdistance selection by parametric search, Information Processing Letters, v.30 n.1, p.9-14, January 1989 [doi>10.1016/0020-0190(89)90166-X]
• 246: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 247: 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]
• 248: Elmar Schömer , Jürgen Sellen , Marek Teichmann , Chee-Keng Yap, Efficient Algorithms for the Smallest Enclosing Cylinder Problem, Proceedings of the 8th Canadian Conference on Computational Geometry, p.264-269, August 12-15, 1996
• 249: SCHROETER, P. AND BIG~IN, J. 1995. Hierarchical image segmentation by multi-dimensional clustering and orientation-adaptive boundary refinement. Patt. Recogn. 28, 695-709.
• 250: 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]
• 251: SEIDEL, R. 1993. Backwards analysis of randomized geometric algorithms. In New Trends in Discrete and Computational Geometry, J. Pach, Ed., Springer-Verlag, Heidelberg, 37- 68.
• 252: Sandeep Sen, Parallel multidimensional search using approximation algorithms: with applications to linear-programming and related problems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237564]
• 253: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 254: SHAFER, L. AND STEIGER, W. 1993. Randomizing optimal geometric algorithms. In Proceedings of the Fifth Canadian Conference on Computational Geometry, 133-138.
• 255: SHARIR, M. 1997. A near-linear algorithm for the planar 2-center problem. Discrete Comput. Geom. 18, 125-134.
• 256: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 257: Micha Sharir , Sivan Toledo, Extremal polygon containment problems, Computational Geometry: Theory and Applications, v.4 n.2, p.99-118, June 1994 [doi>10.1016/0925-7721(94)90011-6]
• 258: 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
• 259: 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]
• 260: SOMMERVILLE, D. M.Y. 1951. Analytical Geometry in Three Dimensions. Cambridge University Press, Cambridge, UK.
• 261: Andrew Stein , Michael Werman, Finding the repeated median regression line, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.409-413, September 1992, Orlando, Florida, United States
• 262: STEIN, A. AND WERMAN, M. 1992b. Robust statistics in shape fitting. In Proceedings of the IEEE International Conference on Computer Vision Pattern Recognition, 540-546.
• 263: Kurt Swanson , D. T. Lee , Vanban L. Wu, An optimal algorithm for roundness determination on convex polygons, Computational Geometry: Theory and Applications, v.5 n.4, p.225-235, Nov. 1995 [doi>10.1016/0925-7721(95)00004-6]
• 264: Samuel M. Thomas , Y. T. Chan, A simple approach for the estimation of circular arc center and its radius, Computer Vision, Graphics, and Image Processing, v.45 n.3, p.362-370, March 1989 [doi>10.1016/0734-189X(89)90088-1]
• 265: TOLEDO, S. 1991. Extremal polygon containment problems and other issues in parametric searching. M.S. Thesis, Dept. of Computer Science, Tel Aviv University, Tel Aviv.
• 266: Sivan Toledo, Approximate parametric searching, Information Processing Letters, v.47 n.1, p.1-4, Aug. 9, 1993 [doi>10.1016/0020-0190(93)90149-4]
• 267: TOLEDO, S. 1993b. Maximizing non-linear concave functions in fixed dimension. In Complexity in Numerical Computations, P. M. Pardalos, Ed., World Scientific, Singapore, 429-447.
• 268: VALIANT, L. 1975. Parallelism in comparison problems. SIAM J. Comput. 4, 348-355.
• 269: Kasturi R. Varadarajan, Approximating monotone polygonal curves using the uniform metric, Proceedings of the twelfth annual symposium on Computational geometry, p.311-318, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237400]
• 270: VARADARAJAN, K. R. AND AGARWAL, P. K. 1995. Linear approximation of simple objects. In Proceedings of the Seventh Canadian Conference on Computational Geometry, 13-18.
• 271: VOELCKER, H. 1993. Current perspective on tolerancing and metrology. Man. Rev. 6, 258- 268.
• 272: WELZL, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, H. Maurer, Ed., LNCS 555, Springer-Verlag, 359-370.
• 273: WESOLOWSKY, G. 1993. The Weber problem: History and perspective. Loca. Sci. 1, 5-23.
• 274: Kyu-Young Whang , Ju-Won Song , Ji-Woong Chang , Ji-Yun Kim , Wan-Sup Cho , Chong-Mok Park , Il-Yeol Song, Octree-R: An Adaptive Octree for Efficient Ray Tracing, IEEE Transactions on Visualization and Computer Graphics, v.1 n.4, p.343-349, December 1995 [doi>10.1109/2945.485621]
• 275: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]
• 276: Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
• 277: ZEMEL, E. 1987. A linear time randomizing algorithm for searching ranked functions. Algorithmica 2, 81-90.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  A. General Literature

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design

Keywords:
clustering, collision detection, linear programming, matrix searching, parametric searching, proximity problems, prune-and-search, randomized algorithms