Computational geometry

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational geometry: a retrospective

Full text

Pdf (2.20 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 75 - 94

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Bernard Chazelle

Department of Computer Science, Princeton University, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 63, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/195058.195110 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, Partitioning arrangements of lines, part II: applications, Discrete & Computational Geometry, v.5 n.6, p.533-573, Sep. 1990 [doi>10.1007/BF02187809]
	2	Pankaj K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, SIAM Journal on Computing, v.21 n.3, p.540-570, June 1992 [doi>10.1137/0221035]
	3	Pankaj K. Agarwal , Boris Aronov, Counting facets and incidences, Discrete & Computational Geometry, v.7 n.4, p.359-369, 1992 [doi>10.1007/BF02187848]
	4	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]
	5	Agarwal, P.K., Matou#ek, J. Range searching with semialgebraic sets, Disc. Comput. Geom. (1994), in press.
	6	Pankaj K. Agarwal , Micha Sharir, Applications of a new space-partitioning technique, Discrete & Computational Geometry, v.9 n.1, p.11-38, 1993 [doi>10.1007/BF02189304]
	7	P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
	8	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	9	K P Agarwal , Micha Sharir , Sivan Toledo, An Efficient Multi-Dimensional Searching Technique and itsApplications, Duke University, Durham, NC, 1993
	10	Aggarwal, A., Chazelle, B., Guibaz, L.J., O'Dfinlaing, C., Yap, C.K. Parallel computational geometry, Algorithmica, 3 (1988), 293-327.
	11	Miklos Ajtai , Nimrod Megiddo, A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.327-338, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129744]
	12	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	13	Alon, N., B~r~ny, I., Fiiredi, Z., Kleitman, D. Point selections and weak e-nets for convex hulls, Combinatorics, Probability and Computing, 3 (1992), 189-200.
	14	Alon. N., Coldrelch. O., Hastad, J., Pera}ta, R. Simple constructions of almost k-wise independent random variables, Random Structures & Algorithms, 3 (1992), 289-304.
	15	Alon, N., Spencer, J.H. The Probabilistic Method, John Wiley & Sons, 1992.
	16	Esther M. Arkin , L. Paul Chew , David P. Huttenlocher , Klara Kedem , Joseph S. B. Mitchell, An efficiently computable metric for comparing polygonal shapes, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.129-137, January 22-24, 1990, San Francisco, California, United States
	17	Boris Aronov , Jiří Matoušek , Micha Sharir, On the sum of squares of cell complexities in hyperplane arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.307-313, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109682]
	18	Boris Aronov , Marco Pellegrini , Micha Sharir, On the zone of a surface in a hyperplane arrangement, Discrete & Computational Geometry, v.9 n.2, p.177-186, 1993 [doi>10.1007/BF02189317]
	19	Aronov, B., Sharir, M. Triangles in space or building (and analyzing) castles in the air, Combinatorica, 10 (1990), 137-173.
	20	Boris Aronov , Micha Sharir, Castles in the air revisited, Proceedings of the eighth annual symposium on Computational geometry, p.146-156, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142710]
	21	Aronov, B., Sharir, M. The union of convex polyhedra in three dimensions, Proc. 34th Ann. IEEE Symp. Foundat. Comput. Sci. (1993), 518-527.
	22	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	23	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	24	Chanderjit L. Bajaj , Tamal K. Dey, Convex decomposition of polyhedra and robustness, SIAM Journal on Computing, v.21 n.2, p.339-364, April 1992 [doi>10.1137/0221025]
	25	Basu, S., Pollack, R., Roy, M.-F. On the combinato. rial and algebraic complexity of quantifier elimination, manuscript, 1994.
	26	Basu, S., Pollack, R., Roy, M.-F. A new algorithm to find a point in every cell defined by a family of polynomials, in "Quantifier Elimination and Cylindrical Algebraic Decomposition", ed. B. Caviness and J. Johnson, Springer-Verlag, to appear.
	27	Saugata Basu , Richard Pollack , Marie-Françoise Roy, Computing a set of points meeting every cell defined by a family of polynomials on a variety, Proceedings of the workshop on Algorithmic foundations of robotics, p.537-555, May 1995, San Francisco, California, United States
	28	Beck, J. An algorithmic approach to the Lovdsz local lemma. L Random Structures & Algorithms, 2 (1991), 343-365.
	29	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	30	Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
	31	Bentley, J.L., Ottmann, T.A. Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., C-28 (1979), 643-647.
	32	Bonnie Berger, Simulating (logcn)-wise independence in NC, Journal of the ACM (JACM), v.38 n.4, p.1026-1046, Oct. 1991 [doi>10.1145/115234.115347]
	33	Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.454-477, December 1994, Research Triangle Park, North Carolina, United States
	34	Marshall Bern, Compatible tetrahedralizations, Proceedings of the ninth annual symposium on Computational geometry, p.281-288, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161151]
	35	Marshall Bern , David Dobkin , David Eppstein, Triangulating polygons without large angles, Proceedings of the eighth annual symposium on Computational geometry, p.222-231, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142722]
	36	Bern, M., Eppstein, D. Mesh generation and optimal triangulation, in: Computing in Euclidean Geometry, 1, World Scientific, ed. D. Z. Du and F. K. Hwang (1992), 23-90.
	37	Bern, M., Eppstein, D., Gilbert, J. Provably 9ood mesh generation, Ptoc. 31st Ann. IEEE Syrup. Foundat. Comput. Sci. (1990), 231-241.
	38	Anders Björner , László Lovász , Andrew C. C. Yao, Linear decision trees: volume estimates and topological bounds, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.170-177, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129730]
	39	Bochnak, J., Coste, M., Roy. M.-F. Gdomdtrie algdbrique rdelle, Springer Verlag, I-Ieidelberg, 1987.
	40	Jean-Daniel Boissonnat , Olivier Devillers , René Schott , Monique Teillaud , Mariette Yvinec, Applications of random sampling to on-line algorithms in computational geometry, Discrete & Computational Geometry, v.8 n.1, p.51-71, 1992 [doi>10.1007/BF02293035]
	41	Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
	42	Br6nnimann, H., Ch#zelle, B., Matou#ek, J. Product range spaces, sensitive sampling, and derandomization, Proc. 34th Ann. IEEE Syrup. Foundat. Comput. Sci. (1993), 400-409.
	43	BrSnnimann, H., Chazelle, B., Pach, J. How hard is halfspace range searching?# Disc. Comput. Geom.# 10 (1993), 143-155.
	44	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	45	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	46	John Canny, Generalised characteristic polynomials, Journal of Symbolic Computation, v.9 n.3, p.241-250, March 1990 [doi>10.1016/S0747-7171(08)80012-0]
	47	Canny, J. Some Practical Tools for Algebraic Geometry, Tech. Rep., Spring school on robot motion planning, Promotion Esprit, 1993.
	48	Canny, J. Computing road maps #n general semialgebraic sets, The Computer Journal, 36 (1993), 504- 514.
	49	Canny, J. Improved algorithms for sign determination and existential quantifier elimination, The Computer Journal, 36 (1993), 409-418.
	50	John Canny , Bruce Donald , Eugene K. Ressler, A rational rotation method for robust geometric algorithms, Proceedings of the eighth annual symposium on Computational geometry, p.251-260, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142726]
	51	Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
	52	Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
	53	Chazelle, B. Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc., 2 (1989), 637- 666.
	54	Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
	55	Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
	56	Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
	57	Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
	58	Chazelle, B. An optimal convex hull algorithm in any fixed dimension, Disc. Comput. Geom., 10 (1993), 377- 409.
	59	Chazelle, B., Dobkin, D.P. Optimal convex decompositions, Computational Geometry, G.T. Toussaint, ed., North-Holland (1985), 63-133.
	60	Bernard Chazelle , Herbert Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Journal of the ACM (JACM), v.39 n.1, p.1-54, Jan. 1992 [doi>10.1145/147508.147511]
	61	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , John Hershberger , Micha Sharir , Jack Snoeyink, Ray shooting in polygons using Geodesic triangulations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.661-673, June 1991, Madrid, Spain
	62	Bernard Chazelle , Herbert Edelsbrunner , Michelangelo Grigni , Leonidas Guibas , Micha Sharir , Emo Welzl, Improved bounds on weak &egr;-nets for convex sets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.495-504, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167222]
	63	B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
	64	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]
	65	Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M. Diameter, width, closest line pair, and parametric searching, Disc. Comput. Geom., 10 (1993), 183-196.
	66	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir , Jack Snoeyink, Computing a face in an arrangement of line segments and related problems, SIAM Journal on Computing, v.22 n.6, p.1286-1302, Dec. 1993 [doi>10.1137/0222077]
	67	Chazelle, B., Friedman, J. A deterministic view of random sampling and its use in geometry, Combinatorica, 10 (1990), 229-249.
	68	B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989 [doi>10.1007/BF02187747]
	69	Chazelle, B., Guibas, L.J. Fractional cascading: L A data structuring technique, IL Applications, Algorithmic#, 1 (1986), 133-162 and 163-191.
	70	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	71	Bernard Chazelle , Jiří Matoušek, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Computational Geometry: Theory and Applications, v.5 n.1, p.27-32, March 1995 [doi>10.1016/0925-7721(94)00018-Q]
	72	Bernard Chazelle , Leonidas Palios, Triangulating a nonconvex polytope, Discrete & Computational Geometry, v.5 n.5, p.505-526, 1990 [doi>10.1007/BF02187807]
	73	Bernard Chazelle , Burton Rosenberg, Lower Bounds on the Complexity of Simplex Range Reporting on a Pointer Machine, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.439-449, July 13-17, 1992
	74	B. Chazelle , M. Sharir, An algorithm for generalized point location and its applications, Journal of Symbolic Computation, v.10 n.3-4, p.281-309, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80065-X]
	75	Ch#zelle, B., Sharir, M., Welzl, E. Quasi-optimal up. per bounds for simplex range searching and new zor#e theorems, Algorithmica, 8 (1992), 407-429.
	76	Bernard Chazelle , Nadia Shouraboura, Bounds on the size of tetrahedralizations, Proceedings of the tenth annual symposium on Computational geometry, p.231-239, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177975]
	77	B. Chazelle , E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete & Computational Geometry, v.4 n.5, p.467-489, 1989 [doi>10.1007/BF02187743]
	78	Siu Wing Cheng , Ravi Janardan, New results on dynamic planar point location, SIAM Journal on Computing, v.21 n.5, p.972-999, Oct. 1992 [doi>10.1137/0221057]
	79	Yi-Jen Chiang , Franco P. Preparata , Roberto Tamassia, A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.44-53, January 25-27, 1993, Austin, Texas, United States
	80	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]
	81	Clarkson, K.L. New applications of random sampling in computational geometry, Disc. Comput. Geom., 2 (1987), 195-222.
	82	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	83	Clarkson, K.L. Las Vegas algorithm for linear programming when the dimension is small, Proc. 29th Ann. IEEE Syrup. Foundat. Comput. Sci. (1988), 452-457.
	84	Clarkson, K.L. Safe and effective determinant evaluatzon, Proc. 33rd Ann. IEEE Symp. Foundat. Comput. Sci. (1992), 387-395.
	85	Clarkson, K.L. Randomized geometric algorithms, in Computing in Euclidean Geometry, D.-Z. Du and F.K. Kwang ed., Lecture Notes Series on Comput. 1 (1992), World Scientific, 117-162.
	86	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	87	Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four Results on Randomized Incremental Constructions, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.463-474, February 13-15, 1992
	88	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]
	89	K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Discrete & Computational Geometry, v.4 n.5, p.423-432, 1989 [doi>10.1007/BF02187741]
	90	E. Cohen , N. Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.523-534, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73057]
	91	Michael F. Cohen , John Wallace , Pat Hanrahan, Radiosity and realistic image synthesis, Academic Press Professional, Inc., San Diego, CA, 1993
	92	Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
	93	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]
	94	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]
	95	Richard Cole , Micha Sharir, Visibility problems for polyhedral terrains, Journal of Symbolic Computation, v.7 n.1, p.11-30, Jan. 1989 [doi>10.1016/S0747-7171(89)80003-3]
	96	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]
	97	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
	98	Cox, D., Little, J., O'Shea, D. Ideals, Varieties, and Algorithms, Springer-Verlag, 1992.
	99	H Crapo , J Ryan, Scene analysis and geometric homology, Proceedings of the second annual symposium on Computational geometry, p.125-132, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10529]
	100	James H. Davenport , Joos Heintz, Real quantifier elimination is doubly exponential, Journal of Symbolic Computation, v.5 n.1-2, p.29-35, February/April 1988 [doi>10.1016/S0747-7171(88)80004-X]
	101	Cecil Jose A. Delfinado , Herbert Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes, Proceedings of the ninth annual symposium on Computational geometry, p.232-239, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161140]
	102	Devillers, O. Randomization yields simple O(n log* n) algorithms for difficult w(n) problems, Int. J. Comput. Geom. Appl., 2 (1992), 97-111.
	103	Olivier Devillers , Stefan Meiser , Monique Teillaud, Fully dynamic Delaunay triangulation in logarithmic expected time per operation, Computational Geometry: Theory and Applications, v.2 n.2, p.55-80, Oct. 1992 [doi>10.1016/0925-7721(92)90025-N]
	104	Tamal K. Dey, Triangulation and CSG representation of polyhedra with arbitrary genus, Proceedings of the seventh annual symposium on Computational geometry, p.364-371, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109689]
	105	Dey, T. Optimal algorithms to detect null-homologous cycles on 2-manifolds, Proc. 5th Canad. Conf. Compu,t. Geom. (1993), 273-278.
	106	Dobkin, D.P., Kirkpatrick, D.G. Fast detection ofpolyhedral intersection, Theoret. Comput. Sci., 27 (1983), 241-253.
	107	D. P. Dobkin , D. Silver, Recipes for geometry and numerical analysis - Part I: an empirical study, Proceedings of the fourth annual symposium on Computational geometry, p.93-105, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73404]
	108	Bruce R. Donald, A geometric approach to error detection and recovery for robot motion planning with uncertainty, Artificial Intelligence, v.37 n.1-3, p.223-271, Dec. 1988 [doi>10.1016/0004-3702(88)90056-2]
	109	Bruce Randall Donald , David Renpan Chang, On the complexity of computing the homology type of a triangulation, Proceedings of the 32nd annual symposium on Foundations of computer science, p.650-661, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185432]
	110	Bruce Donald , Patrick Xavier , John Canny , John Reif, Kinodynamic motion planning, Journal of the ACM (JACM), v.40 n.5, p.1048-1066, Nov. 1993 [doi>10.1145/174147.174150]
	111	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]
	112	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]
	113	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]
	114	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	115	Herbert Edelsbrunner, The union of balls and its dual shape, Proceedings of the ninth annual symposium on Computational geometry, p.218-231, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161139]
	116	H. Edelsbrunner , L. Guibas , J. Hershberger , R. Seidel , M. Sharir , J. Snoeyink , E. Welzl, Implicitly representing arrangements of lines or segments, Discrete & Computational Geometry, v.4 n.5, p.433-466, 1989 [doi>10.1007/BF02187742]
	117	Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
	118	Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, The complexity of many cells in arrangements of planes and related problems, Discrete & Computational Geometry, v.5 n.2, p.197-216, 1990 [doi>10.1007/BF02187785]
	119	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	120	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	121	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	122	Herbert Edelsbrunner , Raimund Seidel , Micha Sharir, On the zone theorem for hyperplane arrangements, SIAM Journal on Computing, v.22 n.2, p.418-429, April 1993 [doi>10.1137/0222031]
	123	Herbert Edelsbrunner , Nimish R. Shah, Triangulating topological spaces, Proceedings of the tenth annual symposium on Computational geometry, p.285-292, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178010]
	124	Ioannis Emiris , John Canny, A general approach to removing degeneracies, Proceedings of the 32nd annual symposium on Foundations of computer science, p.405-413, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185399]
	125	Erickson, J., Seidel, R. Better lower bounds on detecting al'fine and spherical degeneracies, Proc. 34th Ann. IEEE Symp. Foundat. Comput. Sci. (1993), 528-536.
	126	Fitchas, N., Galligo, A., Morgenstern, J. Algorithmes rap#cles en#eque" nt#el et en parallel 29o,,r l#,#l;m;nat;on de quantificateurs en ggomdtrie dldmentaire, S#minaire Structures Ordonn#es, U.E.R. Math. Univ. Paris VII, 1987.
	127	Fortune, S. A sweepline algorithm }or Voronoi diagrams, Algorithmica, 2 (1987), 153-174.
	128	Fortune, S. Stable maintenance of point-set triangulation in two dimensions, manuscript, AT&T Bell Laboratories. Abbreviated version appeared in: Proc. 30th Ann. Syrup. Foundat. Comput. Sci. (1989), 494-499.
	129	Steven Fortune, Numerical stability of algorithms for 2D Delaunay triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.83-92, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142695]
	130	Fortune, S. Voronoi diagrams and Delaunay triangulatzons, in: Computing in Euclidean Geometry, eds: D.-Z. Du, F. Hwang, 1, World Scientific (1992), 193- 233.
	131	Fortune, S. Computational Geometry, ed. R. Martin, Directions in Computational Geometry, Information Geometers, to appear.
	132	Steven Fortune , Victor Milenkovic, Numerical stability of algorithms for line arrangements, Proceedings of the seventh annual symposium on Computational geometry, p.334-341, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109685]
	133	Steven Fortune , Christopher J. Van Wyk, Efficient exact arithmetic for computational geometry, Proceedings of the ninth annual symposium on Computational geometry, p.163-172, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161015]
	134	Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
	135	Fredman, M.L. Lower bounds on the complexity of some optimal data structures, SIAM J. Comput., 10 (1981), 1-10.
	136	Freedman, M.H. Identi/ying attractors via homology: a manuscript, 1991.
	137	G#rtner, B. A subexponential algomthm }or abstract optzmization problems, Proc. 33rd Ann. IEEE Syrup. Foundat. Comput. Sci. (1992), 464-472.
	138	Garey, M.R., Johnson, D.S., Preparata, F.P., Tarjan, R.E. Triangulating a simple polygon, Inform. Process. Lett., 7 (1978), 175-180.
	139	Glassner, A.S. Ray Tracing, Academic Press, 1989.
	140	Goodman, J.E., Pollack, R. Multidimensional sorting, SIAM J. Comput., 12 (1983), 484-507.
	141	Goodman, J.E., Pollack, R. Upper bounds .for configurations and polytopes in 1##, Disc. Comput. Geom., 1 (1986), 219-227.
	142	Goodman, J.E., Pollack, R., Sturmfels, B. The intrinsic spread o/ a configuration is R#, J. Amer. Math. Soc., 3 (1990), 639-651.
	143	Goodman, J.E., Pollack, R., Wenger, R. Geomett:ic transversal theory, in: New Trends in Discrete and Computational Geometry, ed. J. Pach, Algorithms and Combinatorics, 10, Springer-Verlag (1993), 163-198.
	144	Michael T. Goodrich, Planar separators and parallel polygon triangulation (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.507-516, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129762]
	145	Goodrich, M. T. Constructing arrangements optimally in parallel, Disc. Comput. Geom., 9 (1993), 371-385.
	146	Michael T. Goodrich , Mikhail J. Atallah , Mark H. Overmars, Output-sensitive methods for rectilinear hidden surface removal, Information and Computation, v.107 n.1, p.1-24, Nov. 1993 [doi>10.1006/inco.1993.1059]
	147	Michael T. Goodrich , Roberto Tamassia, Dynamic trees and dynamic point location, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.523-533, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103472]
	148	Michael T. Goodrich , Roberto Tamassia, Dynamic ray shooting and shortest paths via balanced geodesic triangulations, Proceedings of the ninth annual symposium on Computational geometry, p.318-327, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161157]
	149	Graham, R.L. An efficient algorithm for determining the convex hull of a planar point set, Inform. Process. Lett., 1 (1972), 132-133.
	150	Greene, D., Yao, F. Finite-resolution computational geometry, Proc. 27th Ann. Symp. Foundat. Comput. Sci. (1986), 143-152.
	151	D. Yu. Grigor'ev, Complexity of deciding Tarski algebra, Journal of Symbolic Computation, v.5 n.1-2, p.65-108, February/April 1988 [doi>10.1016/S0747-7171(88)80006-3]
	152	D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
	153	Guibas, L.J., Knuth, D.,E., Sharir, M. Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 7 (1992), 381-413.
	154	Guibas, L.J., Overmars, M., Sharir, M. Ray shooting, implicit point location, and related queries in arrangements of segments, Tech. Rep. 433, New York Univ., March 1989.
	155	D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
	156	Guibas, L.J., Sharir, M. Combinatorics and algomthms of arrangements, New Trends in Discrete and Computational Geometry, J. Pach, ed., 1993, Springer-Verlag, 9-#6.
	157	Dan Halperin , Micha Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Proceedings of the ninth annual symposium on Computational geometry, p.11-18, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160989]
	158	Dan Halperin , Micha Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions, Proceedings of the tenth annual symposium on Computational geometry, p.11-20, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177436]
	159	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	160	Haussler, D., Welzl, E. e-nets and simplex range queries, Disc. Comput. Geom., 2 (1987), 127-151.
	161	Heintz, J., Roy, M.-F., Solern6, P. On the complexity of semi-algebraic sets, Proc. IFIP San Francisco, North- Holland (1989), 293-298.
	162	Heintz, J., Roy, M.-F., Solern6, P. Sur la complexitd du principe de Tarskz.Seidenberg, Bull. Soc. Math. France, 118 (1990), 101-126.
	163	Heintz, J., Recio, T., Roy, M.-F. Algorithms in real algebraic geometry and applications to computational geometry, Discrete and Computational Geometry, Dim#cs Series 6, AMS-ACM, ed. J.E. Goodman, R. Pollack, W. Steiger (1991), 137-163.
	164	John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.54-63, January 25-27, 1993, Austin, Texas, United States
	165	Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	166	C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
	167	Christoph M. Hoffmann , John E. Hopcroft , Michael E. Karasick, Robust Set Operations on Polyhedral Solids, IEEE Computer Graphics and Applications, v.9 n.6, p.50-59, November 1989 [doi>10.1109/38.41469]
	168	J E Hopcroft , G T Wolfong, Reducing multiple object motion planning to graph searching, SIAM Journal on Computing, v.15 n.3, p.768-785, August 1986 [doi>10.1137/0215055]
	169	Daniel P Huttenlocher, Three-Dimensional Recognition of Solid Objects from a Two- Dimensional Image, Massachusetts Institute of Technology, Cambridge, MA, 1988
	170	Impagliazzo, R., Zuckerman, D. How to recycle random bits, Proc. 30th Ann. IEEE Syrup. Foundat. Comput. Sci. (1989), 248-253.
	171	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]
	172	Michael Karasick , Derek Lieber , Lee R. Nackman, Efficient Delaunay triangulation using rational arithmetic, ACM Transactions on Graphics (TOG), v.10 n.1, p.71-91, Jan. 1991 [doi>10.1145/99902.99905]
	173	M. S. Karasick, On the representation and manipulation of rigid solids, McGill University, Montreal, Que., Canada, 1989
	174	Katz, M., Sharir, M. Optimal slope selection via expanders, Proc. 5th Canad. Conf. Comput. Geom. (a998), 139-144.
	175	Kirkpatrick, D.G. Optimal search in planar subdivisions, SIAM J. Comput., 12 (1983), 28-35.
	176	David G. Kirkpatrick , Maria M. Klawe , Robert E. Tarjan, Polygon triangulation in O(n log log n) time with simple data structures, Discrete & Computational Geometry, v.7 n.4, p.329-346, 1992 [doi>10.1007/BF02187846]
	177	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	178	R. Klein, Abstract Voronoi diagrams and their applications (extended abstract), Proceedings on International Workshop on Computational Geometry on Computational Geometry and its Applications, p.148-157, October 1988, Wu:9Airzburg, Germany
	179	Zhenyu Li , Victor Milenkovic, Constructing strongly convex hulls using exact or rounded arithmetic, Proceedings of the sixth annual symposium on Computational geometry, p.235-243, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98577]
	180	Lipton, R.J., Tarjan, R.E. Applications of a planar separator theorem, SIAM 3. Comput., 9 (1980), 615- 627.
	181	Jiří Matoušek , Chi-Yuan Lo , William Steiger, Ham-sandwich cuts in R^d, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.539-545, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129765]
	182	M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
	183	Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
	184	Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
	185	Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
	186	Matou#ek, J. Range searching with efficient h,erarchical cuttings, Disc. Comput. Geom., 10 (1993), 157-182.
	187	Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
	188	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]
	189	Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
	190	Matou#ek, J. Geometric range searching, Tech. Report B-93-09, Free Univ. Berlin, 1993.
	191	Jiří Matoušek , Otfried Schwarzkopf, A deterministic algorithm for the three-dimensional diameter problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.478-484, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167217]
	192	Matou#ek, J., Schwarzkopf, O. On ray ,:hooting in convex polytopes, Disc. Comput. Geom., 10 (1993), 215- 232.
	193	Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
	194	Matou#ek, J., Welzl, E., Wernisch, L. Discrepancy and e-approximations for bounded VC-dimension# Combinatorica, 13 (1993), 455-466.
	195	Megiddo, N. Combinatorial optimization with rational objective functions, Mathematics of Operations Iresearch, 4 (1979), 414-424.
	196	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]
	197	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]
	198	Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
	199	Kurt Mehlhorn , Klaus Simon, Intersecting two polyhedra one of which is convex, Fundamentals of Computation Theory, p.534-542, September 09-13, 1985
	200	Kurt Mehlhorn , Chee-Keng Yap, Constructive Whitney-Graustein theorem: or how to untangle closed planar curves, SIAM Journal on Computing, v.20 n.4, p.603-621, Aug. 1991 [doi>10.1137/0220038]
	201	Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
	202	Victor Joseph Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, 1988
	203	Milenkovic, V. Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic, Proc. 30th Ann. IEEE Symp. Foundat. Comput. Sci. (1989), 500-505.
	204	Milenkovic, V. Rounding face lattices in the plane, Abstracts 1st Canad. Conf. Comput. Geom. (1989), 12.
	205	Milenkovic, V. Rounding face lattices in d dimensions, Proc. 2nd Canad. Conf. Comput. Geom. (1990), 40-45.
	206	Bhubaneswar Mishra, Algorithmic algebra, Springer-Verlag New York, Inc., New York, NY, 1993
	207	Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
	208	Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
	209	Muller, D.E., Preparata, F.P. Finding the intersection of two convex polyhedra, Theoret. Comput. Sci., 7 (1978), 217-236.
	210	Mulmuley, K. A fast planar partition algorithm 1, Proc. 29th Ann. IEEE Syrup. Foundat. Comput. Sci. (1988), 580-589.
	211	Mulmuley, K. On obstructions in relation to a fixed viewpoint, Proc. 30th Ann. IEEE Symp. Foundat. Comput. Sci. (1989), 592-597.
	212	Ketan Mulmuley, On levels in arrangements and Voronoi diagrams, Discrete & Computational Geometry, v.6 n.4, p.307-338, 1991 [doi>10.1007/BF02574692]
	213	Kentan Mulmuley, A fast planar partition algorithm, II, Journal of the ACM (JACM), v.38 n.1, p.74-103, Jan. 1991 [doi>10.1145/102782.102785]
	214	Ketan Mulmuley, Hidden surface removal with respect to a moving view point, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.512-522, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103471]
	215	Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109662]
	216	Ketan Mulmuley, Randomized multidimensional search trees: lazy balancing and dynamic shuffling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.180-196, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185368]
	217	Ketan Mulmuley, Randomized multidimensional search trees: further results in dynamic sampling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.216-227, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185371]
	218	Mulmuley, K. Randomized geometric algorithms and pseudo-random generators, Proc. 33rd Ann. IEEE Syrup. Foundat. Comput. Sci. (1992), 90-100.
	219	Mulmuley# K. Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.
	220	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	221	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]
	222	Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
	223	Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994
	224	Pach, J., Agarwal, P.K. Combinatorial Geometry, John Wiley & Sons, in press.
	225	János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992 [doi>10.1007/BF02187829]
	226	Pellegrini, M. Ray shooting on triangles in 3- dimensional space, Algorithmica, 9 (1993), 471-494.
	227	Marco Pellegrini, On point location and motion planning among simplices, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.95-104, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195112]
	228	Poll#ck, R., Roy, M.-F. On the number of cells defined by a set of polynomials, Compte-Rendus, 316 (1993), 573-577.
	229	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	230	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	231	Preparata, F.P., Tamassia, R. Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th Ann. IEEE Symp. Foundat. Comput. Sci. (1988), 558-567.
	232	Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
	233	David Prill, On approximations and incidence in cylindrical algebraic decompositions, SIAM Journal on Computing, v.15 n.4, p.972-993, Nov. 1986 [doi>10.1137/0215069]
	234	Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
	235	Ramos, E., Intersection of unit-balls and diameter of a set of points in R3, manuscript, 1994.
	236	Reif, J.H., Sen, S. Optimal randomized parallel algorithms for computational geometry, Algorithmica, 7 (1992), 91-117.
	237	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	238	Jim Ruppert , Raimund Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra., Discrete & Computational Geometry, v.7 n.3, p.227-253, 1992 [doi>10.1007/BF02187840]
	239	Saalfeld, A. Divide_and_conquer in early algebraic topology: the Mayer-Vietoris exact homology sequence revisited, Abstracts 1st Canad. Conf. Comput. Geom. (1989), 11.
	240	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]
	241	Haijo Schipper, Determining contractibility of curves, Proceedings of the eighth annual symposium on Computational geometry, p.358-367, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142749]
	242	Schwartz, J.T., Sharir, M. On the "piano movers" problem. II: General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math., 4 (1983), 298-35.1.
	243	Jacob T. Schwartz , Micha Sharir, Algorithmic motion planning in robotics, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	244	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	245	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	246	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]
	247	Raimund Seidel, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry: Theory and Applications, v.1 n.1, p.51-64, July 1991 [doi>10.1016/S0925-7721(99)00042-5]
	248	Seidel, R. Backward analysis of randomized geometric algorithms, New Trends in Discrete and Computational Geometry, J. Pach, ed., 1993, Springer-Verlag, 37-67.
	249	Seidel, R. The nature and meaning of perturbations zn geometric computing, manuscript, 1994.
	250	Shamos, M.I., Hoey, D. Closest-point .problems, Proc. 16th Ann. IEEE Symp. Foundat. Comput. Sci. (1975), 151-162.
	251	Sharir, M. Almost tight upper bound,, for lower envelopes in higher dimensions, Proc. 34th Ann. IEEE Symp. Foundat. Comput. Sci. (1993), 498-507.
	252	Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
	253	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
	254	Spencer, J.H. Ten Lectures on the Probabzhstic Method, CBMS-NSF, SIAM, 1987.
	255	Sugihara, K., Iri, M. Construction of the Voronoi diagram for one milhon generators in single precision arithmetic, First Canad. Conf. Comput. Geom., 1989.
	256	K. Sugihara , M. Iri, A solid modelling system free from topological inconsistency, Journal of Information Processing, v.12 n.4, p.380-393, 1989
	257	Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]
	258	G. Tourlakis , J. Mylopoulos, Some Results in Computational Topology, Journal of the ACM (JACM), v.20 n.3, p.439-455, July 1973 [doi>10.1145/321765.321776]
	259	Pravin M. Vaidya, Space-time trade-offs for orthogonal range queries, SIAM Journal on Computing, v.18 n.4, p.748-758, Aug. 1989 [doi>10.1137/0218051]
	260	Vapnik, V.N., Chervonenkis, A. Ya. On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16 (1971), 264- 280.
	261	G. Vegter, Kink-free deformations of polygons, Proceedings of the fifth annual symposium on Computational geometry, p.61-68, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73840]
	262	Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]
	263	Volker Weispfenning, The complexity of linear problems in fields, Journal of Symbolic Computation, v.5 n.1-2, p.3-27, February/April 1988 [doi>10.1016/S0747-7171(88)80003-8]
	264	E. Welzl, Partition trees for triangle counting and other range searching problems, Proceedings of the fourth annual symposium on Computational geometry, p.23-33, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73397]
	265	Welzl, E., On spanning trees with low crossing numbers, Tech. Rep. TR B 92-02, Free University, Berlin, 1992.
	266	Whitney, H. Elementary structure of real algebraic va. rieties, Annals of Math., 66 (1957).
	267	Willard, D.E. Polygon retrieval, SIAM J. Comput., 11 (1982), 149-165.
	268	Y#o, A.C. On the complexity of maintaining partial sums, SIAM J. Comput., 14 (1985), 277-288.
	269	Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]
	270	Y#o, A.C. Lower bounds for algebraic computation trees with integer inputs, Proc. 30th Ann. IEEE Syrup. Foundat. Comput. Sci. (1989), 308-313.
	271	F. Frances Yao, Computational geometry, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	272	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]
	273	C.-K. Yap, Symbolic treatment of geometric degeneracies, Journal of Symbolic Computation, v.10 n.3-4, p.349-370, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80069-7]
	274	Chee-Keng Yap, A geometric consistency theorem for a symbolic perturbation scheme, Journal of Computer and System Sciences, v.40 n.1, p.2-18, February 1990 [doi>10.1016/0022-0000(90)90016-E]
	275	Yap, C.K. Towards exact geometric computation, Proc. 5th Canad. Conf. Comput. Geom. (1993), 405- 419.

CITED BY 7

	Felipe Cucker , Marek Karpinski , Pascal Koiran , Thomas Lickteig , Kai Werther, On real Turing machines that toss coins, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.335-342, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Bernard Chazelle, Lower bounds for off-line range searching, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.733-740, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Edgar Chávez , Gonzalo Navarro, Probabilistic proximity search: fighting the curse of dimensionality in metric spaces, Information Processing Letters, v.85 n.1, p.39-46, 16 January 2003
	Saugata Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.408-417, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Saugata Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, Journal of the ACM (JACM), v.46 n.4, p.537-555, July 1999
	Domenico Cantone , Alfredo Ferro , Alfredo Pulvirenti , Diego Reforgiato Recupero , Dennis Shasha, Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.535-550, April 2005
	Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001