Geometric range searching

ABSTRACT

In geometric range searching, algorithmic problems of the following type are considered. Given an n-point set P in the plane, build a data structure so that, given a query triangle R, the number of points of P lying in R can be determined quickly. Similar questions can be asked for point sets in higher dimensions, with triangles replaced by simplices or by more complicated shapes. Algorithms of this type are of crucial importance in computational geometry, as they can be used as subroutines in solutions to many seemingly unrelated problems, which are often motivated by practical applications, for instance in computer graphics (ray tracing, hidden-surface removal etc.). We present a survey of theoretical results and the main techniques in geometric range searching.

REFERENCES

• 1: K P Agarwal, On Stabbing Lines for Convex Polyhedra in 3D, Duke University, Durham, NC, 1993
• 2: AGARWAL, P. K. 1991. Geometrjc partitioning and its applications. In Computational Geometry: Papers from the DIMACS Special Year, J E. Goodman, R. Pollack, and W. Steiger, Eds. American Mathematical Society.
• 3: 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]
• 4: AGARWAL, P. K. AND MATOUSEK, J. 1994. On range searching with semialgebraic sets. Discrete Comput. Geom 11, 393-418.
• 5: 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]
• 6: K P Agarwal , Jiri Matousek, Dynamic Half-Space Range Reporting and Its Application, Duke University, Durham, NC, 1991
• 7: 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]
• 8: AGARWAL, P. K., ARONOV, B., SHARIR, M., AND SURI, S. 1993. Selecting distances in the plane. Algorithmic 9, 495-513.
• 9: 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
• 10: Pankaj K. Agarwal , Marco Pellegrini , Micha Sharir, Counting circular arc intersections, SIAM Journal on Computing, v.22 n.4, p.778-793, Aug. 1993 [doi>10.1137/0222050]
• 11: A. Aggarwal , M. Hansen , T. Leighton, Solving query-retrieval problems by compacting Voronoi diagrams, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.331-340, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100260]
• 12: N. Alon , D. Haussler , E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, Proceedings of the third annual symposium on Computational geometry, p.331-340, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41994]
• 13: 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]
• 14: 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]
• 15: David Avis, Non-partitionable point sets, Information Processing Letters, v.19 n.3, p.125-129, Oct. 1984 [doi>10.1016/0020-0190(84)90090-5]
• 16: Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
• 17: BENTLEY, J. L. AND SAXE, J. B. 1980. Decomposable searching problems I: Static-to-dynamic transformation. J. Alg. 1, 301-358
• 18: BRONNIMMVN, H., CHAZELLE, B., AND PACH, J, 1993, How hard is halfspace rmge searching. Discrete Comput. Geom. 10, 143-155.
• 19: Christoph Burnikel , Kurt Mehlhorn , Stefan Schirra, On degeneracy in geometric computations, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.16-23, January 23-25, 1994, Arlington, Virginia, United States
• 20: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 21: CHAZELLE, B. 1993b. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10, 377-409.
• 22: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 23: 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]
• 24: CHAZELLE, B. 1989. Lower bounds on the complexity of polytope range searching. J. Am. Math. Sot. 2, 637-666.
• 25: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 26: 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]
• 27: Bernard Chazelle , Joel Friedman, Point location among hyperplanes and unidirectional ray-shooting, Computational Geometry: Theory and Applications, v.4 n.2, p.53-62, June 1994 [doi>10.1016/0925-7721(94)90009-4]
• 28: CHAZELLE, B. AND FRIEDW, J. 1990. A deterministic view of random sampling and its use in geometry. Combmatorlca 10, 3, 229-249.
• 29: 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
• 30: B. Chazelle , F. P. Preparata, Halfspace range search: an algorithmic application of k-sets, Discrete & Computational Geometry, v.1 n.1, p.83-93, 1986 [doi>10.1007/BF02187685]
• 31: 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
• 32: CHAZELLE, B. AND ROSENBERG, B. 1991. The complexity of computing partial sums off-line. Int. J. Comput. Geom. Appl, 1, 1,33-45.
• 33: 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]
• 34: B Chazelle , R Cole , P Preparata , C Yap, New upper bounds for neighbor searching, Information and Control, v.68 n.1-3, p.105-124, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80030-4]
• 35: CHAZELLE, B., EDELSBRUNNER, H., GUIBAS, L., AND SKARIR, M. 1993. Diameter, width, closest line pair and parametrm searching, Dkscrete Comput. Geom. 10, 183-196.
• 36: 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]
• 37: 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]
• 38: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 39: CHAZELLE, B., SHARIR, M,, AND WELZL, E. 1992. Quasi-optimal upper bounds for simplex range searching and new zone theorems. AlgorMzmica 8, 407-429.
• 40: L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
• 41: Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
• 42: K. L. Clarkson, Applications of random sampling in computational geometry, II, Proceedings of the fourth annual symposium on Computational geometry, p.1-11, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73394]
• 43: 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]
• 44: CLARKSON, K. L. 1987. New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195-222.
• 45: 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]
• 46: K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161004]
• 47: Edith Cohen , Nimrod Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs, Journal of the ACM (JACM), v.40 n.4, p.791-830, Sept. 1993 [doi>10.1145/153724.153727]
• 48: 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]
• 49: Richard Cole, Partitioning Point Sets in 4 Dimensions, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.111-119, July 15-19, 1985
• 50: Richard Cole , Chee K Yap, Geometric retrieval problems, Information and Control, v.63 n.1-2, p.39-57, Oct/Nov. 1984 [doi>10.1016/S0019-9958(84)80040-6]
• 51: 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]
• 52: 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]
• 53: DE BERG, M., HALPERIN, D., OVERMARS, M., SNOEYINK, J., AND VAN KREVELD, M. 1994. Efficient ray shooting and hidden surface removal. Algorithmic 12, 30-53.
• 54: DILLENCOURT, M. B., MOUNT, D. M,, AND NE- TANYAHU, N. S. 1992. A randomized algorithm for slope selection. Int. J. Comput. Geom. Appl. 2, 1-27.
• 55: David P. Dobkin , Herbert Edelsbrunner, Space searching for intersecting objects, Journal of Algorithms, v.8 n.5, p.348-361, Sept. 1987 [doi>10.1016/0196-6774(87)90015-0]
• 56: DOBKIN, D. AND EDELSBRUNNER, H. 1984. Organizing point sets in two and three dimensions. Tech. Rep. F130, Technische Univ. Graz, Graz, Austria.
• 57: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 58: EDELSBRUNNER, H. AND HUBER, F. 1984. Dissecting sets of points in two and three dimensions, Rep. F138, Inst. Informationsverarb., Tech. Univ. Graz, Graz, Austria.
• 59: 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]
• 60: H Edelsbrunner , E Welzl, Halfplanar range search in linear space and O(n0.695) query time, Information Processing Letters, v.23 n.6, p.289-293, Dec. 3, 1986
• 61: 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]
• 62: EDELSBRUNNER, H., KIRKPATRICK, D. G., AND MAURER, H. A. 1982. Polygonal intersection searching. In/ Process. Lett. 14, 74-79.
• 63: 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]
• 64: 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]
• 65: Ioannis Emiris , John Canny, An efficient approach to removing geometric degeneracies, Proceedings of the eighth annual symposium on Computational geometry, p.74-82, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142694]
• 66: 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]
• 67: FREDMAN, M. L. 1981. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput. 10, 1-10.
• 68: Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
• 69: GOODMAN, J. E., POLLACK, R., AND STEIGER, W., EDS. 1991. Computational Geometry: Papers from the DIMACS Special Year. American Mathematical Society, Providence, R.I.
• 70: Dan Gusfield, Parametric Combinatorial Computing and a Problem of Program Module Distribution, Journal of the ACM (JACM), v.30 n.3, p.551-563, July 1983 [doi>10.1145/2402.322391]
• 71: 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]
• 72: HALPERIN, D. AND SHARIR, M, 1994. New bounds for lower envelopes in three dimension, with applications to visibility in terrains. Discrete Comput. Geom. 12, 313-326.
• 73: HARRIS, J, 1992, Algebraic Geometry (A Frost Course). Springer-Verlag, Berhn.
• 74: David Haussler, SPHERE PACKING NUMBERS FOR SUBSETS OF THE BOOLEAN n-CUBE WITH BOUNDED VAPNIK-CHERVONENKIS DIMENSION, University of California at Santa Cruz, Santa Cruz, CA, 1991
• 75: HAUSSLER, D. AND WELZL, E. 1987. Epsdonnets and simplex range queries. Discrete Comput. Geom. 2, 127-151.
• 76: Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161137]
• 77: KOML6S, J., SZEMERtiDI, E., AND PINTZ, J. 1982. A lower bound for Hedbronn's problem J. London Math. Sot, 25, 2, 13-24.
• 78: LIPTON, R. J. ANII TAKJAN, R. E. 1980, Applications of a planar separator theorem, SL4M J. Comput 9, 615-627.
• 79: MATOU3EK, J. 1994 Tight upper bounds for the discrepancy of halfspaces. KAM Series in Discrete Mathematics, (Tech. Rep ), Charles Univ, Prague. To appear in Discrete Comput. Geom
• 80: Jiří Matoušek, Linear optimization queries, Journal of Algorithms, v.14 n.3, p.432-448, May 1993 [doi>10.1006/jagm.1993.1023]
• 81: Jiří Matoušek, On vertical ray shooting in arrangements, Computational Geometry: Theory and Applications, v.2 n.5, p.279-285, March 1993 [doi>10.1016/0925-7721(93)90024-Z]
• 82: MATOUSEK J. 1993. Range searching with efficient hierarchical cuttings Dzscrete Comput Geom. 10, 2, 157-182.
• 83: 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]
• 84: Jiří Matoušek, Efficient partition trees, Discrete & Computational Geometry, v.8 n.3, p.315-334, 1992 [doi>10.1007/BF02293051]
• 85: 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]
• 86: 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]
• 87: Jiří Matoušek, Cutting hyperplane arrangements, Discrete & Computational Geometry, v.6 n.5, p.385-406, 1991 [doi>10.1007/BF02574697]
• 88: Jiří Matoušek, Construction of &egr;-nets, Discrete & Computational Geometry, v.5 n.5, p.427-448, 1990 [doi>10.1007/BF02187804]
• 89: MATOU3EK, J. AND SCHWARZKOPF, O. 1993 On ray shooting in convex polytopes. Discr Comput Geom. 10, 2, 215-232
• 90: MATOUi5EK, J. AND SPENCER, J. 1994. Discrepancy m anthmetlc progressions, KAM Series (Tech. Report), Charles Umv., Prague. Also to appear in Am. J. Math.
• 91: Jiří Matoušek , Emo Welzl, Good splitters for counting points in triangles, Journal of Algorithms, v.13 n.2, p.307-319, June, 1992 [doi>10.1016/0196-6774(92)90021-4]
• 92: MATOU5EK, J., WELZL, E , AND WERNISCH, L. 1993 Discrepancy and e-approximations for bounded VC-dimension Combinatorics 13, 455-466
• 93: 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]
• 94: MEGIDDO, N, 1979, Combinatorial optimization with rational objective functions. Math, Oper. Res. 4, 414-424.
• 95: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 96: MOHABAN, S AND SHARIR, M 1993 Ray shooting amidst spheres m three dimensions and related problems Manuscript, Tel Aviv Univ
• 97: MULMULEY, K, 1993 Computational Geometry. An Introduction Through Randomized Algorithms Prentice-Hall, Englewood Cliffs, NJ
• 98: MULMULEY, K, 1992, Randomized geometric algorithms and pseudo-random generators. In Proceedings of the 33rd Annual IEEE Symposium on the Foundation of Computer Science. IEEE, New York, 90-100,
• 99: 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]
• 100: 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]
• 101: 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]
• 102: 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]
• 103: MULMULEY, K. 1988. A fast planar partition algorithm, I. In Proceedings of the 29th Annual IEEE Symposmm on the Foundations of Computer Sczence. IEEE, New York, 580-589.
• 104: 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]
• 105: M. H. Overmars , H. Schipper , M. Sharir, Storing line segments in partition trees, BIT, v.30 n.3, p.385-403, 1990 [doi>10.1007/BF01931656]
• 106: Mark H. Overmars, Efficient data structures for range searching on a grid, Journal of Algorithms, v.9 n.2, p.254-275, June 1988 [doi>10.1016/0196-6774(88)90041-7]
• 107: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 108: PACH, J. ED. 1993. New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 10. Springer-Verlag, Berlin.
• 109: PATERSON, M. S. AND YAO, F. F. 1986. Point retrieval for polygons. J. Alg. 7, 441-447.
• 110: Marco Pellegrini, Incidence and nearest-neighbor problems for lines in 3-space, Proceedings of the eighth annual symposium on Computational geometry, p.130-137, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142703]
• 111: M. Pellegrini , P. W. Shor, Finding stabbing lines in 3-space, Discrete & Computational Geometry, v.8 n.2, p.191-208, 1992 [doi>10.1007/BF02293043]
• 112: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 113: 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]
• 114: RASIN, M. O. 1976. Probabilistic algorithms. In Algorithms and Complexity, J. F. Traub, Ed. Academic Press, New York, 21-30.
• 115: ROTH, K. 1976. Developments in the triangle problem. Adu. Math. 22, 364-385.
• 116: Haijo Schipper , Mark H. Overmars, Dynamic partition trees, BIT, v.31 n.3, p.421-436, Summer 1991 [doi>10.1007/BF01933260]
• 117: Otfried Schwarzkopf, Ray shooting in convex polytopes, Proceedings of the eighth annual symposium on Computational geometry, p.286-295, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142734]
• 118: Otfried Schwarzkopf, Dynamic maintenance of geometric structures made easy, Proceedings of the 32nd annual symposium on Foundations of computer science, p.197-206, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185369]
• 119: Raimund Seidel, The Nature and Meaning of Perturbations in Geometric Computing, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.3-17, February 24-26, 1994
• 120: 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]
• 121: 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]
• 122: SHARIR, M. 1993. Almost tight upper bounds for lower envelopes in higher dimensions. In Proceedings of the 34th Annual IEEE Symposium on the Foundations of Computer Science (FOGS 93). IEEE, New York, 498-507.
• 123: Emo Welzl, On Spanning Trees with Low Crossing Numbers, Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, p.233-249, January 1992
• 124: 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]
• 125: Dan E. Willard, New data structures for orthogonal range queries, SIAM Journal on Computing, v.14 n.1, p.232-253, Feb. 1985 [doi>10.1137/0214019]
• 126: WILLARD, D. E. 1982. Polygon retrieval. SIAM J. Comput. 11, 149-165.
• 127: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]
• 128: F. Frances Yao, A 3-space partition and its applications, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.258-263, December 1983 [doi>10.1145/800061.808755]
• 129: 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]
• 130: F. Frances Yao , David P. Dobkin , Herbert Edelsbrunner , Michael S. Paterson, Partitioning space for range queries, SIAM Journal on Computing, v.18 n.2, p.371-384, April 1989 [doi>10.1137/0218025]

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:
  E. Data

  G. Mathematics of Computing

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory

Keywords:
computational geometry, lower bounds in arithmetic model, partition tree, range searching