|
A. |
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.
Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd ed., 2000. (course textbook) |
B. |
H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001. |
C. |
J. E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition,
CRC Press LLC, Boca Raton, FL, 2004. |
D. |
M. Goossens, F. Mittelbach and A. Samarin. The LATEX Companion, Addison Wesley, 1994 |
E. |
K. Mulmuley, Computational Geometry: An Introduction Through
Randomized Algorithms, Prentice Hall, Englewood Cliffs, NJ, 1994. |
F. |
J. O'Rourke, Computational Geometry in C, 2nd edition, Cambridge
University Press, New York, 1998. |
G. |
J.-R. Sack and J. Urrutia (eds.), Handbook of Computational
Geometry. North-Holland, 2000. |
|
A. |
A. Björner, L. Lovász, and A.C. Yao. Linear decision trees: Volume estimates and topological bounds. In Proc. 24th Annu. ACM Sympos. Theory Comput., pp. 170-177, 1993.
Link |
B. |
B. Chazelle and B. Rosenberg. Computing partial sums in multidimensional arrays. In Proc. 5th Annu. ACM Sympos. Comput. Geom., pp. 131-139, 1989.
Link |
C. |
F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985. |
D. |
A.C. Yao. Decision tree complexity and betti numbers. In Proc. 25th Annu. ACM Sympos. Theory Comput., 1994. Link |
| |
|
A. |
Hervé Brönnimann, Bernard Chazelle, and Jiri Matousek. Product range spaces, sensitive sampling, and derandomization. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci., pp. 400-409, 1993.
Link |
B. |
Timothy M. Y. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 10-19, 1995. Link |
C. |
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
Link |
D. |
Seidel, R. Convex Hull Computations.
Ch. 19 in Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.). CRC Press, Boca Raton, FL, pp. 361-375, 1997. |
E. |
R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comput. Geom. Theory Appl., 5:115-116, 1995. Link |
F. | G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, 1994. |
| |
|
A. |
Ivan J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 211-219, 1995.
Link |
B. |
J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979. |
C. |
B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992.
Link |
D. |
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
Link |
E. |
D. P. Dobkin, and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381-392, 1985.
Link |
F. |
D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. Computing the intersection-depth of polyhedra. Algorithmica, 9:518-533, 1993.
Link |
| |
|
A. |
P. K. Agarwal. Range searching, CRC Handbook of Discrete and Computational Geometry, 2nd ed., (J. Goodman and J. O’Rourke, eds.), CRC Press, New York, 2004, pp.809-837. Link |
B. |
P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, Contemp. Math. 223, Amer. Math. Soc. Press, 1999, pp. 1-56. Link |
C. |
B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986. |
D. |
B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163-191, 1986. |
E. |
H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15:317-340, 1986. Link |
F. |
K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag, 1984 |
G. |
K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215-241, 1990 |
H. |
F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21:267-280, 1992. Link |
I. |
N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM , 29:669-679, 1986. Link |
J. |
J. Snoeyink. Point location. CRC Handbook of Discrete and Computational Geometry, 2nd ed., (J. Goodman and J. O’Rourke, eds.), CRC Press, New York, 2004, pp.809-837. pp. 767-786. |
| |
|
A. |
F. Aurenhammer and R. Klein. Voronoi diagrams. In Handbook of Computational Geometry (J.R. Sack and J. Urrutia, Eds.). North Holland, 1998. Link |
B. |
P.B. Callahan and S.R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest neighbors and potential fields. JACM, 42: 67-90, 1995. Link |
C. |
H. Edelsbrunner.
Geometry and Topology for Mesh Generation. Cambridge University Press, 2001. |
D. |
S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.
Link |
E. |
L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992. |
F. |
M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995. |
| |
|
A. |
P.K. Agarwal and M. Sharir. Arrangements and their applications. In Handbook of Computational Geometry (J. Sack and J. Urrutia, eds.). North-Holland, New York, pp. 49-119, 2000. Link |
B. |
J. Matousek. Lower envelopes. Ch 7 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002. |
C. |
J. Matousek. Number of faces in arrangements. Ch 6 in Lectures on
Discrete Geometry. Springer-Verlag, New York, 2002. |
D. |
J. Pach and P.K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995 (Chapters 10, 11) |
| |
|
A. |
M. Bern. Triangulations and mesh generation. In Handbook of Discrete and Computational Geometry, 2nd ed. (J. E. Goodman and J. O'Rourke, eds.). CRC Press, New York, pp. 563-582, 2004. |
B. |
H. Edelsbrunner. Triangle Meshes. Ch. 2 in Geometry and Topology for Mesh
Generation. Cambridge University Press, 2001. |
C. |
R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl. 1:51-64, 1991. Link |
| |
|
|
General Reading: |
A. |
P.K. Agarwal. Range searching, CRC Handbook of Discrete and Computational Geometry, 2nd ed., (J. Goodman and J. O’Rourke, eds.), CRC Press, New York, 2004, pp.809-837. Link |
B. |
P.K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, Contemp. Math. 223, Amer. Math. Soc. Press, 1998, pp. 1-56. Link |
C. |
P.K. Agarwal, S. Har-Peled, and K.R. Varadarajan, Geometric approximation via coresets, in Current Trends in Combinatorial and Computational Geometry (E. Welzl, ed.), Cambridge University Press, New York, to appear. Link |
D. |
B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press., 2000. |
E. |
J. Pach and P.K. Agarwal. Combinatorial Geometry, Wiley Interscience, 1995 (Chapters 15, 16). |
|
For Lecture 18: |
F. |
J. Matousek. Ch. 10 in Lectures on Discrete Geometry. Springer-Verlag New York, 2002. |
G. |
J. Pach and P.K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995. |
|
For Lecture 19: |
H. |
J. Matousek. Lectures on Discrete Geometry. Springer-Verlag, New York, 2002. |
|
For Lecture 20: |
I. |
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Ch. 16 in Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd ed., 2000. |
J. |
P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete Comput. Geom., Contemp. Math. 223, Amer. Math. Soc. Press, 1999, pp. 1-56. Link |
|
For Lecture 21 |
K. |
J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992. |
| |
|
|
For Lectures 22 and 23: |
A. |
R. Motwani and P. Raghavan. Ch 9 in Randomized algorithms. Cambridge University Press, 1995. |
|
For Lecture 24: |
A. |
P.K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998. Link |
| |
|
|
For General Reading: |
A. |
P.K. Agarwal, S. Har-Peled, and K.R. Varadarajan. Approximating extent measures of points. J. ACM. 4:606-635, 2004. Link |
B. |
D. Dobkin and D. Kirkpatrick. Determining the separation of preprocessed polyhedra -- a unified approach. LNCS 443: 400-413, 1990. Link |
C. |
R.M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory 10: 227-236, 1974. |
|
For Lecture 26: |
A. |
J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991. |
B. |
M. Sharir. Algorithmic motion planning. In Handbook of Discrete and Computational Geometry (J. E. Goodman and J. O'Rourke, eds.). CRC Press, Boca Raton, FL, pp. 733-754, 1997.
|
|