Yao [Yao82] has shown that a partial-sum query under the semigroup model can be answered in time; a matching lower bound is proved by Chazelle and Rosenberg [CR89].

**BLY93**-
Anders Björner, László Lovász, and Andrew Chi-Chih Yao.
Linear decision trees: Volume estimates and topological bounds.
In
*Proc. 24th Annu. ACM Sympos. Theory Comput.*, pages 170-177, 1993. **BO94**-
Michael Ben-Or.
Algebraic computation trees in characteristi
*p*>0. In*Proc. 35th Annual Symposium on Foundations of Computer Science*, pages 534-539, 1994. **CR89**-
B. Chazelle and B. Rosenberg.
Computing partial sums in multidimensional arrays.
In
*Proc. 5th Annu. ACM Sympos. Comput. Geom.*, pages 131-139, 1989. **Fre81**-
M. L. Fredman.
A lower bound on the complexity of orthogonal range queries.
*J. ACM*, 28:696-705, 1981. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **SY82**-
J. M. Steele and A. C. Yao.
Lower bounds for algebraic decision trees.
*J. Algorithms*, 3:1-8, 1982. **Tar83**-
R. E. Tarjan.
*Data Structures and Network Algorithms*, volume 44 of*CBMS-NSF Regional Conference Series in Applied Mathematics*. Society for Industrial Applied Mathematics, 1983. **Yao82**-
A. C. Yao.
Space-time trade-off for answering range queries.
In
*Proc. 14th Annu. ACM Sympos. Theory Comput.*, pages 128-136, 1982. **Yao91**-
A. C. Yao.
Lower bounds for algebraic computation trees with integer inputs.
*SIAM J. Comput.*, 20:655-668, 1991. **Yao94**-
Andrew Chi-Chih Yao.
Decision tree complexity and betti numbers.
In
*Proc. 25th Annu. ACM Sympos. Theory Comput.*, 1994.

The best known algorithm for segment-intersection counting runs in time roughly [GOS88, Aga90, Cha93]. Developing a faster algorithm, proving a nontrivial lower bound, is a challenging open problem.

**Aga90**-
Pankaj K. Agarwal.
Partitioning arrangements of lines: II. Applications.
*Discrete Comput. Geom.*, 5:533-573, 1990. **BO79**-
J. L. Bentley and T. A. Ottmann.
Algorithms for reporting and counting geometric intersections.
*IEEE Trans. Comput.*, C-28:643-647, 1979. **Bro81**-
K. Q. Brown.
Comments on ``Algorithms for reporting and counting geometric
intersections''.
*IEEE Trans. Comput.*, C-30:147-148, 1981. **Cha93**-
B. Chazelle.
Cutting hyperplanes for divide-and-conquer.
*Discrete Comput. Geom.*, 9(2):145-158, 1993. **GOS88**-
L. Guibas, M. Overmars, and M. Sharir.
Intersecting line segments, ray shooting, and other applications of
geometric partitioning techniques.
In
*Proc. 1st Scand. Workshop Algorithm Theory*, volume 318 of*Lecture Notes in Computer Science*, pages 64-73. Springer-Verlag, 1988. **IKO88**-
C. Icking, R. Klein, and T. Ottmann.
Priority search trees in secondary memory.
In
*Proc. Internat. Workshop Graph-Theoret. Concepts Comput. Sci. (WG '87)*, volume 314 of*Lecture Notes in Computer Science*, pages 84-93. Springer-Verlag, 1988. **McC85**-
E. M. McCreight.
Priority search trees.
*SIAM J. Comput.*, 14:257-276, 1985. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985.

Definition, Graham scan algorithm, Jarvis march, quick hull, computing tangents and point location, on-line algorithm. All this material can be found in Chapter 3 of Preparata and Shamos [PS85]. An optimal -time algorithm is due to Chan [Cha95]; see also [KS86] for an earlier, more complex optimal algorithm. Convex hull of a simple polygon can be computed in linear time [GY83].

**Bal95**-
Ivan J. Balaban.
An optimal algorithm for finding segment intersections.
In
*Proc. 11th Annu. ACM Sympos. Comput. Geom.*, pages 211-219, 1995. **BO79**-
J. L. Bentley and T. A. Ottmann.
Algorithms for reporting and counting geometric intersections.
*IEEE Trans. Comput.*, C-28:643-647, 1979. **Bro81**-
K. Q. Brown.
Comments on ``Algorithms for reporting and counting geometric
intersections''.
*IEEE Trans. Comput.*, C-30:147-148, 1981. **CE92**-
B. Chazelle and H. Edelsbrunner.
An optimal algorithm for intersecting line segments in the plane.
*J. ACM*, 39:1-54, 1992. **Cha95**-
Timothy M. Y. Chan.
Output-sensitive results on convex hulls, extreme points, and related
problems.
In
*Proc. 11th Annu. ACM Sympos. Comput. Geom.*, pages 10-19, 1995. **CS89**-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
*Discrete Comput. Geom.*, 4:387-421, 1989. **GY83**-
R. L. Graham and F. F. Yao.
Finding the convex hull of a simple polygon.
*J. Algorithms*, 4:324-331, 1983. **KS86**-
D. G. Kirkpatrick and R. Seidel.
The ultimate planar convex hull algorithm?
*SIAM J. Comput.*, 15:287-299, 1986. **Mul90**-
K. Mulmuley.
A fast planar partition algorithm, I.
*Journal of Symbolic Computation*, 10(3/4):253-280, 1990. **Mul91**-
K. Mulmuley.
A fast planar partition algorithm, II.
*J. ACM*, 38:74-103, 1991. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **PS91**-
J. Pach and M. Sharir.
On vertical visibility in arrangements of segments and the queue size
in the Bentley-Ottman line sweeping algorithm.
*SIAM J. Comput.*, 20:460-470, 1991.

Definition, faces, examples of polytopes, moment curve,
upper-bound theorem (complexity of a convex *d*-polytope), duality.
The book by Ziegler is an excellent treatise on convex polytopes
[Zie94]. See also the books by Edelsbrunner [Ede87].
A simple proof of the upper-bound theorem is given by Seidel
[Sei95].

Incremental algorithm (also known as the *beneath-beyond*
method) [PS85, Section3.4,], finer analysis of the
incremental algorithm [Sei81], [Ede87, Section8.4,],
divide-and-conquer algorithm [Ede87, Section8.5,].

**Ede87**-
H. Edelsbrunner.
*Algorithms in Combinatorial Geometry*, volume 10 of*EATCS Monographs on Theoretical Computer Science*. Springer-Verlag, Heidelberg, 1987. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **Sei81**-
R. Seidel.
A convex hull algorithm optimal for point sets in even dimensions.
M.Sc. thesis, Dept. Comput. Sci., Univ. British Columbia,
Vancouver, BC, 1981.
Report 81/14.
**Sei95**-
R. Seidel.
The upper bound theorem for polytopes: an easy proof of its
asymptotic version.
*Comput. Geom. Theory Appl.*, 5:115-116, 1995. **Zie94**-
G. M. Ziegler.
*Lectures on Polytopes*, volume 152 of*Graduate Texts in Mathematics*. Springer-Verlag, 1994.

A randomized incremental algorithm for computing the convex hull
of a set of points in *d*-space with expected running
time .
The original algorithms is by
Clarkson and Shor [CS89] and Seidel
[Sei91].
The algorithm presented in the class is based on the
exposition in [MR95, Mul94].
These algorithms were derandomized by Chazelle
[Cha93] and subsequently simplified by
Brönnimann et al. [BCM93].
See [AGR94] for a parallel convex hull algorithms
based on Chazelle's algorithm.

**AGR94**-
N. M. Amato, M. T. Goodrich, and E. A. Ramos.
Parallel algorithms for higher-dimensional convex hulls.
In
*Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 683-694, 1994. **BCM93**-
Hervé Brönnimann, Bernard Chazelle, and Jir´i Matousek.
Product range spaces, sensitive sampling, and derandomization.
In
*Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 400-409, 1993. **Cha93**-
B. Chazelle.
An optimal convex hull algorithm in any fixed dimension.
*Discrete Comput. Geom.*, 10:377-409, 1993. **CS89**-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
*Discrete Comput. Geom.*, 4:387-421, 1989. **MR95**-
R. Motwani and P. Raghavan.
*Randomized Algorithms*. Cambridge University Press, New York, NY, 1995. **Mul94**-
K. Mulmuley.
*Computational Geometry: An Introduction Through Randomized Algorithms*. Prentice Hall, Englewood Cliffs, NJ, 1994. **Sei91**-
R. Seidel.
Small-dimensional linear programming and convex hulls made easy.
*Discrete Comput. Geom.*, 6:423-434, 1991.

A randomized incremental algorithm, with
expected time, for reporting all
*k* intersection points in a set of *n* segments.
Such algorithms are described in
[CS89, Mul90, Mul91, CEG 93].
Deterministic algorithms with the same time are presented in
[CE92, Bal95].

Antipodal pairs, normal diagram, diameter and width in 2D. Randomized algorithm for computing the diameter of a point set in 3D [CS89]. Near-linear-time deterministic algorithms for computing the diameter in 3D are presented in [CEGS93, MS96, Ram96, AGR94].

**AGR94**-
N. M. Amato, M. T. Goodrich, and E. A. Ramos.
Parallel algorithms for higher-dimensional convex hulls.
In
*Proc. 35th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 683-694, 1994. **Bal95**-
Ivan J. Balaban.
An optimal algorithm for finding segment intersections.
In
*Proc. 11th Annu. ACM Sympos. Comput. Geom.*, pages 211-219, 1995. **CE92**-
B. Chazelle and H. Edelsbrunner.
An optimal algorithm for intersecting line segments in the plane.
*J. ACM*, 39:1-54, 1992. **CEG 93**-
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink.
Computing a face in an arrangement of line segments and related
problems.
*SIAM J. Comput.*, 22:1286-1302, 1993. **CEGS93**-
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir.
Diameter, width, closest line pair and parametric searching.
*Discrete Comput. Geom.*, 10:183-196, 1993. **CS89**-
K. L. Clarkson and P. W. Shor.
Applications of random sampling in computational geometry, II.
*Discrete Comput. Geom.*, 4:387-421, 1989. **MS96**-
J. Matousek and O. Schwarzkopf.
A deterministic algorithm for the three-dimensional diameter problem.
*Comput. Geom. Theory Appl.*, 6:253-262, 1996. **Mul90**-
K. Mulmuley.
A fast planar partition algorithm, I.
*Journal of Symbolic Computation*, 10(3/4):253-280, 1990. **Mul91**-
K. Mulmuley.
A fast planar partition algorithm, II.
*J. ACM*, 38:74-103, 1991. **Ram96**-
E. Ramos.
Intersection of unit-balls and diameter of a point set in .
*Computat. Geom. Theory Appl.*, 6:in press, 1996.

Definition, properties of Voronoi diagrams, Delaunay triangulation, relationship between Voronoi diagrams and convex hulls, randomized incremental algorithm.

There are a number of survey papers on Voronoi diagrams, see e.g. [Aur91, For92]. The first time algorithm was developed by Shamos and Hoey [SH75]; see also [PS85]. A sweep-line algorithm for computing the Voronoi diagram of a set of points in the plane was given by Fortune [For87]. The relationship between Voronoi diagrams and lower envelopes is described in [ES86, SA95]. See [Aur91, AS95, BSTY95, CKS 95, CKS 95] and the references therein for some references on Voronoi diagrams of point objects.

The randomized incremental algorithm described in the class is by Guibas et al. [GKS92]. See also [Che86],

**AS95**-
Helmut Alt and Otfried Schwarzkopf.
The Voronoi diagram of curved objects.
In
*Proc. 11th Annu. ACM Sympos. Comput. Geom.*, pages 89-97, 1995. **Aur91**-
F. Aurenhammer.
Voronoi diagrams: A survey of a fundamental geometric data structure.
*ACM Comput. Surv.*, 23:345-405, 1991. **BSTY95**-
Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, and Mariette Yvinec.
Voronoi diagrams in higher dimensions under certain polyhedral
distance functions.
In
*Proc. 11th Annu. ACM Sympos. Comput. Geom.*, pages 79-88, 1995. **Che86**-
L. P. Chew.
Building Voronoi diagrams for convex polygons in linear expected
time.
Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth
College, Hanover, NH, 1986.
**CKS 95**-
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, and Emo Welzl.
Voronoi diagrams of lines in 3-space under polyhedral convex distance
functions.
In
*Proc. 6th ACM-SIAM Sympos. Discrete Algorithms*, pages 197-204, 1995. **ES86**-
H. Edelsbrunner and R. Seidel.
Voronoi diagrams and arrangements.
*Discrete Comput. Geom.*, 1:25-44, 1986. **For87**-
S. J. Fortune.
A sweepline algorithm for Voronoi diagrams.
*Algorithmica*, 2:153-174, 1987. **For92**-
S. Fortune.
Voronoi diagrams and Delaunay triangulations.
In D.-Z. Du and F. K. Hwang, editors,
*Computing in Euclidean Geometry*, volume 1 of*Lecture Notes Series on Computing*, pages 193-233. World Scientific, Singapore, 1992. **GKS92**-
L. J. Guibas, D. E. Knuth, and M. Sharir.
Randomized incremental construction of Delaunay and Voronoi
diagrams.
*Algorithmica*, 7:381-413, 1992. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **SA95**-
M. Sharir and P. K. Agarwal.
*Davenport-Schinzel Sequences and Their Geometric Applications*. Cambridge University Press, New York, 1995. **SH75**-
M. I. Shamos and D. Hoey.
Closest-point problems.
In
*Proc. 16th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 151-162, 1975.

Slab method, persistent data structure, amortized complexity.

The material was taken from the paper by Sarnak and Tarjan [ST86]. The data structure describe here is partially persistent, in the sense that one is not allowed to make changes in the earlier versions of the data structure. See [DSST89] for a fully persistent data structure.

Monotone chain method, improving the space complexity, improving the query time, fractional cascading.

The material covered here can be found in Chapter 2 of the textbook. The improvement in the query time was proposed by Edelsbrunner et al. [EGS86]. The general fractional cascading was introduced by Chazelle and Guibas [CG86a, CG86b]. A dynamic version was proposed by Mehlhorn and Näher [MN90]; see also [Sen92].

Preparata and Tamassia dynamized the monotone-chain method [PT90, PT89, TP90]. By adding persistence to their dyanmic data structures they obtained a three-dimensional point-location data structure [PT92].

**CG86a**-
B. Chazelle and L. J. Guibas.
Fractional cascading: I. A data structuring technique.
*Algorithmica*, 1:133-162, 1986. **CG86b**-
B. Chazelle and L. J. Guibas.
Fractional cascading: II. Applications.
*Algorithmica*, 1:163-191, 1986. **DSST89**-
J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan.
Making data structures persistent.
*J. Comput. Syst. Sci.*, 38:86-124, 1989. **EGS86**-
H. Edelsbrunner, L. J. Guibas, and J. Stolfi.
Optimal point location in a monotone subdivision.
*SIAM J. Comput.*, 15:317-340, 1986. **MN90**-
K. Mehlhorn and S. Näher.
Dynamic fractional cascading.
*Algorithmica*, 5:215-241, 1990. **PT89**-
F. P. Preparata and R. Tamassia.
Fully dynamic point location in a monotone subdivision.
*SIAM J. Comput.*, 18:811-830, 1989. **PT90**-
F. P. Preparata and R. Tamassia.
Dynamic planar point location with optimal query time.
*Theoret. Comput. Sci.*, 74:95-114, 1990. **PT92**-
F. P. Preparata and R. Tamassia.
Efficient point location in a convex spatial cell-complex.
*SIAM J. Comput.*, 21:267-280, 1992. **Sen92**-
S. Sen.
Fractional cascading simplified.
In
*Proc. 3rd Scand. Workshop Algorithm Theory*, volume 621 of*Lecture Notes in Computer Science*, pages 212-220. Springer-Verlag, 1992. **ST86**-
N. Sarnak and R. E. Tarjan.
Planar point location using persistent search trees.
*Commun. ACM*, 29:669-679, 1986. **TP90**-
R. Tamassia and F. P. Preparata.
Dynamic maintenance of planar digraphs, with applications.
*Algorithmica*, 5:509-527, 1990.

Review of simplex and ellipsoid methods, overview of combinatorial algorithms, Megiddo's two-dimensional LP algorithm [Meg83, PS85], Seidel's randomized incremental algorithm [Sei91], Matousek-Sharir-Welzl algorithm [MSW96].

Any book on combinatorial optimization (e.g. [PS82, GLS88, Sch86]) describes simplex and ellipsoid methods. The survey paper by Gärtner and Welzl reviews the known combinatorial algorithms for linear programming in fixed dimensions [PS85].

Matousek et al. [MSW96] describe an abstract framework, called LP-type problems, and show that their algorithm extends to any problem that fits in this framework. See [Ame94, Gär95] for more work on LP-type problems.

**Ame94**-
N. Amenta.
Helly-type theorems and generalized linear programming.
*Discrete Comput. Geom.*, 12:241-261, 1994. **Gär95**-
Bernd Gärtner.
A subexponential algorithm for abstract optimization problems.
*SIAM J. Comput.*, 24:1018-1035, 1995. **GLS88**-
M. Grötschel, L. Lovász, and A. Schrijver.
*Geometric Algorithms and Combinatorial Optimization*, volume 2 of*Algorithms and Combinatorics*. Springer-Verlag, Berlin Heidelberg, 1988. Second edition 1994. **Meg83**-
N. Megiddo.
Linear-time algorithms for linear programming in and
related problems.
*SIAM J. Comput.*, 12:759-776, 1983. **MSW96**-
J. Matousek, M. Sharir, and E. Welzl.
A subexponential bound for linear programming.
*Algorithmica*, 16:498-516, 1996. **PS82**-
C. H. Papadimitriou and K. Steiglitz.
*Combinatorial Optimization: Algorithms and Complexity*. Prentice Hall, Englewood Cliffs, NJ, 1982. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **Sch86**-
A. Schrijver.
*Theory of Linear and Integer Programming*. Wiley-Interscience, New York, NY, 1986. **Sei91**-
R. Seidel.
Small-dimensional linear programming and convex hulls made easy.
*Discrete Comput. Geom.*, 6:423-434, 1991.

Clarkson's randomized algorithm [Cla95]; combining it with Matousek et al. algorithm; LP-type problems.

Selecting the *k*-th leftmost intersection point;
general paradigm.

Clarkson technique for linear programming has also been applied
to some other geometric optimization problems; see e.g.
[BG95, Cla93, AD97].
The parametric searching was introduced by Megiddo
[Meg79, Meg83]. Optimal algorithms for
computing the *k*-leftmost intersection point in a set of lines
are presented in
[CSSS89, Mat91, SS93, KS93, BC94].
A survey of techniques used for geometric optimization can be
found in [AS96].

**AD97**-
Pankaj K. Agarwal and Pavan K. Desikan.
An approximation algorithm for terrain simplification.
In
*Proc. 8th ACM-SIAM Sympos. Discrete Algorithms*, pages 139-147, 1997. **AS96**-
Pankaj K. Agarwal and Micha Sharir.
Efficient algorithms for geoemtric optimization.
Tech. Report CS-1996-19, Dept. Computer Science, Duke University,
1996.
**BC94**-
H. Brönnimann and B. Chazelle.
Optimal slope selection via cuttings.
In
*Proc. 6th Canad. Conf. Comput. Geom.*, pages 99-103, 1994. **BG95**-
H. Brönnimann and M. T. Goodrich.
Almost optimal set covers in finite VC-dimension.
*Discrete Comput. Geom.*, 14:263-279, 1995. **Cla93**-
Kenneth L. Clarkson.
Algorithms for polytope covering and approximation.
In
*Proc. 3rd Workshop Algorithms Data Struct.*, volume 709 of*Lecture Notes Comput. Sci.*, pages 246-252. Springer-Verlag, 1993. **Cla95**-
K. L. Clarkson.
Las Vegas algorithms for linear and integer programming.
*J. ACM*, 42:488-499, 1995. **CSSS89**-
R. Cole, J. Salowe, W. Steiger, and E. Szemerédi.
An optimal-time algorithm for slope selection.
*SIAM J. Comput.*, 18:792-810, 1989. **KS93**-
M. J. Katz and M. Sharir.
Optimal slope selection via expanders.
*Inform. Process. Lett.*, 47:115-122, 1993. **Mat91**-
J. Matousek.
Randomized optimal algorithm for slope selection.
*Inform. Process. Lett.*, 39:183-187, 1991. **Meg79**-
N. Megiddo.
Combinatorial optimization with rational objective functions.
*Math. Oper. Res.*, 4:414-424, 1979. **Meg83**-
N. Megiddo.
Applying parallel computation algorithms in the design of serial
algorithms.
*J. ACM*, 30:852-865, 1983. **SS93**-
L. Shafer and W. Steiger.
Randomizing optimal geometric algorithms.
In
*Proc. 5th Canad. Conf. Comput. Geom.*, pages 133-138, 1993.

Definition, deterministic algorithm for constructing an arrangement, zone theorem, levels, duality, minimum area triangle in a set of points.

Most of the material can be found in the book by Edelsbrunner [Ede87]. The proof of the zone theorem presented in the class is due to Chazelle et al. [CGL85], and can also be found in the book by Pach and Agarwal [PA95]. The paper by Chazelle et al. discusses other applications of duality and arrangements.

Representation of arrangements in higher dimensions, zone theorem, lower envelopes, complexity of a single cell, triangulation. Relationship between lower envelopes and Davenport-Schinzel sequences.

The material was taken from the book by Sharir and Agarwal [SA95]. See also the survey paper by Guibas and Sharir [GS93],

**CGL85**-
B. Chazelle, L. J. Guibas, and D. T. Lee.
The power of geometric duality.
*BIT*, 25:76-90, 1985. **Ede87**-
H. Edelsbrunner.
*Algorithms in Combinatorial Geometry*, volume 10 of*EATCS Monographs on Theoretical Computer Science*. Springer-Verlag, Heidelberg, 1987. **GS93**-
L. Guibas and M. Sharir.
Combinatorics and algorithms of arrangements.
In J. Pach, editor,
*New Trends in Discrete and Computational Geometry*, volume 10 of*Algorithms and Combinatorics*, pages 9-36. Springer-Verlag, 1993. **PA95**-
Janos Pach and Pankaj K. Agarwal.
*Combinatorial Geometry*. John Wiley & Sons, New York, NY, 1995. **SA95**-
M. Sharir and P. K. Agarwal.
*Davenport-Schinzel Sequences and Their Geometric Applications*. Cambridge University Press, New York, 1995.

General searching problem, semigroup model, range trees, fractional cascading, lower bounds, improved bounds.

The data structures can be found in the book by Preparata and Shamos [PS85]. The improved space bound is by Chazelle [Cha86]. An optimal data structure for orthogonal range-counting problem was developed by Chazelle [Cha88]. The lower bounds are proved by Chazelle in [Cha90a, Cha90b].

Partition trees, ham-sandwich theorem, random sampling, cuttings, simplicial partition.

The partition tree discussed in the class is by Willard [Wil82], and the improvement is by Edelsbrunner and Welzl [EW86]. The lower bound on simplex range searching is by Chazelle [Cha89]. The best-known data structure for simplex range searching is by Matousek [Mat93]. The survey papers by Matousek [Mat94] and Agarwal [Aga96] summarize most of the results on simplex range searching and its extensions.

**Aga96**-
Pankaj K. Agarwal.
Range searching.
Report CS-1996-05, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.
**Cha86**-
B. Chazelle.
Filtering search: a new approach to query-answering.
*SIAM J. Comput.*, 15:703-724, 1986. **Cha88**-
B. Chazelle.
A functional approach to data structures and its use in
multidimensional searching.
*SIAM J. Comput.*, 17:427-462, 1988. **Cha89**-
B. Chazelle.
Lower bounds on the complexity of polytope range searching.
*J. Amer. Math. Soc.*, 2:637-666, 1989. **Cha90a**-
B. Chazelle.
Lower bounds for orthogonal range searching, I: the reporting case.
*J. ACM*, 37:200-212, 1990. **Cha90b**-
B. Chazelle.
Lower bounds for orthogonal range searching, II: the arithmetic
model.
*J. ACM*, 37:439-463, 1990. **EW86**-
H. Edelsbrunner and E. Welzl.
Halfplanar range search in linear space and query
time.
*Inform. Process. Lett.*, 23:289-293, 1986. **Mat93**-
J. Matousek.
Range searching with efficient hierarchical cuttings.
*Discrete Comput. Geom.*, 10(2):157-182, 1993. **Mat94**-
J. Matousek.
Geometric range searching.
*ACM Comput. Surv.*, 26:421-461, 1994. **PS85**-
F. P. Preparata and M. I. Shamos.
*Computational Geometry: An Introduction*. Springer-Verlag, New York, 1985. **Wil82**-
D. E. Willard.
Polygon retrieval.
*SIAM J. Comput.*, 11:149-165, 1982.

Quad trees, kd-trees, binary space partitions. Applications of these data structures.

The book by Samet [Sam90] is an excellent source on quad-trees; the kd-trees were introduced by Bentley [Ben75]. The binary space partitions were introduced by Fuchs et al [FKN80] for hidden surface removal. Since then they have been used for in many problems. The first nontrivial theoretical bounds on BSP's were proved by Paterson and Yao [PY90, PY92]. See the paper by Agarwal et al [AGMV96] and the references therein for recent work on BSP's.

**AGMV96**-
P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter.
Binary space partitions for fat rectangles.
In
*Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci.*, October 1996. **Ben75**-
J. L. Bentley.
Multidimensional binary search trees used for associative searching.
*Commun. ACM*, 18(9):509-517, 1975. **FKN80**-
H. Fuchs, Z. M. Kedem, and B. Naylor.
On visible surface generation by a priori tree structures.
*Comput. Graph.*, 14(3):124-133, 1980. Proc. SIGGRAPH '80. **Gre88**-
L. Greengard.
*The rapid evaluation of potential fields in particle systems*. MIT Press, Cambridge, 1988. **Gre90**-
L. Greengard.
The numerical solution of the N-body problem.
*Computers in Physics*, ??:142-152, 1990. **PY90**-
M. S. Paterson and F. F. Yao.
Efficient binary space partitions for hidden-surface removal and
solid modeling.
*Discrete Comput. Geom.*, 5:485-503, 1990. **PY92**-
M. S. Paterson and F. F. Yao.
Optimal binary space partitions for orthogonal objects.
*J. Algorithms*, 13:99-113, 1992. **Sam90**-
H. Samet.
*The Design and Analysis of Spatial Data Structures*. Addison-Wesley, Reading, MA, 1990.

Triangulation with small crossing number [HS95], visibility-map approach [CG89], multi-level data structures [Aga92], parametric searching [AM93]. See the survey paper [Aga96].

Visibility map, painter's algorithm, output-sensitive algorithms, binary space partitions, z-buffer, and volume rendering.

See the monograph by de Berg [dB93] for known results on hidden surface removal in computational geometry. See any book on graphics for graphics algorithms [FvDF 93].

**Aga92**-
Pankaj K. Agarwal.
Ray shooting and other applications of spanning trees with low
stabbing number.
*SIAM J. Comput.*, 21:540-570, 1992. **Aga96**-
Pankaj K. Agarwal.
Range searching.
Report CS-1996-05, Dept. Comput. Sci., Duke Univ., Durham, NC, 1996.
**AM93**-
Pankaj K. Agarwal and J. Matousek.
Ray shooting and parametric search.
*SIAM J. Comput.*, 22(4):794-806, 1993. **CG89**-
B. Chazelle and L. J. Guibas.
Visibility and intersection problems in plane geometry.
*Discrete Comput. Geom.*, 4:551-581, 1989. **dB93**-
M. de Berg.
*Ray Shooting, Depth Orders and Hidden Surface Removal*, volume 703 of*Lecture Notes Comput. Sci.*Springer-Verlag, Berlin, Germany, 1993. **FvDF 93**-
J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, and Phillips.
*Introduction to Computer Graphics*. Addison-Wesley, Reading, MA, 1993. **HS95**-
J. Hershberger and S. Suri.
A pedestrian approach to ray shooting: Shoot a ray, take a walk.
*J. Algorithms*, 18:403-431, 1995.

The survey paper by Schirra gives a good overview of all these topics. See the references in the paper for details. The book by Hoffman [Hof89] is also an excellent source.

**EC91**-
I. Emiris and J. Canny.
A general approach to removing degeneracies.
In
*Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci.*, pages 405-413, 1991. **Ede87**-
H. Edelsbrunner.
*Algorithms in Combinatorial Geometry*, volume 10 of*EATCS Monographs on Theoretical Computer Science*. Springer-Verlag, Heidelberg, 1987. **Hof89**-
C. Hoffmann.
*Geometric and Solid Modeling*. Morgan-Kaufmann, San Mateo, CA, 1989. **Sei94**-
R. Seidel.
The nature and meaning of perturbations in geometric computing.
In
*Proc. 11th Sympos. Theoret. Aspects Comput. Sci.*, volume 775 of*Lecture Notes Comput. Sci.*, pages 3-17. Springer-Verlag, 1994.

Agarwal's Home Page

Return to CPS 234 Homepage.

Thu May 1 00:38:34 EDT 1997