COMPSCI 234
Fall 2011

Reading

Books and Surveys

  1. B. Chazelle. The Discrepancy Method: Randomness and Complexity Cambridge Univ.Press, 2001.[C]
  2. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd ed., 2000. (course textbook) [dBKOS]
  3. H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.[Ed]
  4. J. E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press LLC, Boca Raton, FL, 2004.[GO]
  5. J. Matoušek, Lectures on Discrete Geometry, Springer, 2002. [Ma]
  6. K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, Englewood Cliffs, NJ, 1994.[Mu]
  7. J.Pach and P.K. Agarwal, Combinatorial geometry , Wiley-Interscience, New York, 1995. [PA]
  8. J. O'Rourke, Computational Geometry in C, 2nd edition, Cambridge University Press, New York, 1998.[O]
  9. J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. North-Holland, 2000.[SU]
  10. F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985. [PS]
  11. Sariel Har-peled. Geometric Approximation Algorithms (Mathematical Surveys and Monographs). American Mathematical Society (2011). [HP]

top

Papers

Geometric Fundamentals

  1. 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
  2. B. Chazelle and B. Rosenberg. Computing partial sums in multidimensional arrays. In Proc. 5th Annu. ACM Sympos. Comput. Geom., pp. 131-139, 1989. Link
  3. F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
  4. A.C. Yao. Decision tree complexity and betti numbers. In Proc. 25th Annu. ACM Sympos. Theory Comput., 1994. Link
  5. B. Chazelle, L.J. Guibas, D.T. Lee. The Power of Geometric Duality. BIT 25 (1985), 76-90. [CGL]

top

Geometric Data Structures I

  1. 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
  2. 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
  3. B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986.
  4. B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163-191, 1986.
  5. H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15:317-340, 1986. Link
  6. E.M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257-276, 1985.Link
  7. K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag, 1984
  8. K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215-241, 1990
  9. F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21:267-280, 1992. Link
  10. N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM , 29:669-679, 1986. Link
  11. R. E. Tarjan. Amortized Computational Complexity. SIAM. J. on Algebraic and Discrete Methods, 6:306-318, 1985. Link
  12. 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.

top

Intersection Detection

  1. Ivan J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 211-219, 1995. Link
  2. J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979.
  3. B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992. Link
  4. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. Link
  5. D. P. Dobkin, and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381-392, 1985. Link
  6. D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. Computing the intersection-depth of polyhedra. Algorithmica, 9:518-533, 1993. Link

top

Convex Hull

  1. Hervé Brönnimann, Bernard Chazelle, and Jiri Matousek. Product range spaces, sensitive sampling, and derandomization. In SIAM J. Comput. Volume 28, Issue 5, pp. 1552-1575 (1999) Link
  2. 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
  3. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. Link
  4. 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.
  5. R. Seidel. Small-Dimensional Linear Programming and Convex Hulls Made Easy, DCG 6 (1991) 423-434. [Sei] Link
  6. R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comput. Geom. Theory Appl., 5:115-116, 1995. Link
  7. G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, 1994. LecturesIntersection Detection

top

Proximity Problems

  1. F. Aurenhammer and R. Klein. Voronoi diagrams. In Handbook of Computational Geometry (J.R. Sack and J. Urrutia, Eds.). North Holland, 1998. Link
  2. 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
  3. H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, 2001.
  4. S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987. Link
  5. L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992.
  6. M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

top

Arrangements

  1. 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
  2. T.K. Dey. Improved Bounds for Planar k -Sets and Related Problems. Discrete & Computational Geometry 19(3): 373-382 (1998)Link
  3. J. Matousek. Lower envelopes. Ch 7 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
  4. J. Matousek. Number of faces in arrangements. Ch 6 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
  5. J. Pach and P.K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995 (Chapters 10, 11)

top

Triangulation

  1. 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.
  2. L. P. Chew. Constrained Delaunay triangulations. Proceedings of the third annual symposium on Computational geometry, p.215-222, June 08-10, 1987, Waterloo, Ontario, Canada. Link
  3. H. Edelsbrunner. Triangle Meshes. Ch. 2 in Geometry and Topology for Mesh Generation. Cambridge University Press, 2001.
  4. W. Mulzer and G. Rote. Minimum Weight Triangulation is NP-hard. Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Sedona, USA, 2006, pp. 1-10.Link
  5. Jan Remy and Angelika Steger. A quasi-polynomial time approximation scheme for minimum weight triangulation. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA Link
  6. J. Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. J. Algorithms 18(3): 548-585 (1995) Link
  7. 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
  8. J. R. Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications 22(1-3):21-74, 2002. Link

top

Geometric Sampling

  1. 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. [AHV] Link
  2. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press., 2000.
  3. P. Indyk. Streaming algorithms for geometric problems. In Proc. 24th Intl. Conf. Foundat. Software Tech. Theoret. Comput. Sci., pages 32--34, 2004. Link
  4. J. Matousek. Ch. 10 in Lectures on Discrete Geometry. Springer-Verlag New York, 2002.
  5. J. Matousek. Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
  6. S. Muthukrishnan. Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland Link
  7. J. Pach and P.K. Agarwal. Combinatorial Geometry, Wiley Interscience, 1995 (Chapters 15, 16).
  8. J. Pach and P.K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995.

top

Geometric Data Structures II

  1. 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
  2. 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
  3. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Ch. 16 in Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd ed., 2000.
  4. 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
  5. J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992.

top

Geometric Optimization

    Linear Programming

  1. P.K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998. Link
  2. S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey, Math Programming, 97, 2003.Link
  3. R. Cole, J. Salowe, W. Steiger, and E. Szemerédi. An optimal-time algorithm for slope selection . SIAM J. Comput., 18 (1989), 792-810. Link
  4. G. B. Dantzig. Linear Programming, (Historical Account) Link
  5. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms, J. ACM, 30 (1983), 852-865. Link
  6. R. Motwani and P. Raghavan. Ch 9 in Randomized algorithms. Cambridge University Press, 1995.
  7. Kenneth L. Clarkson: Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. J. ACM 42(2): 488-499 (1995) [Clarkson]

    8. Shape Matching

  8. H. Alt and L. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation, in Handbook of Computational Geometry, (J.-R. Sack and J.Urrutia, eds.), Elsevier, 1999, 121-153.
  9. P. Besl and N. McKay. A method for registration of 3-D shapes. IEEE Trans. on Pattern Analysis and Machine Intelligence, 14 (1992). Link
  10. R. Kolodny, P. Koehl, and M. Levitt. Comprehensive evaluation of protein structure alignment methods: scoring by geometric measures. J. Mol. Biol. , 346, 1173-1188 (2005).
  11. H. Pottmann, Q. Huang, Y. Yang, and S. Hu. Geometry and convergence analysis of algorithms for registration of 3D Shapes. International Journal of Computer Vision , 67(3): 277 - 296, 2006
  12. R. C. Veltkamp, Shape matching: Similarity measures and algorithms. Tech Rept, Utrecht University, 2001.
  13. H. Wolfson and I. Rigoutsos. Geometric hashing: An overview. IEEE Computational Science and Engineering, 4 (1997), 10-21. Link

    14. Clustering

  14. R. Xu and D. Wunsch. Survey of Clustering Algorithms, IEEE Transactions on Neural Networks, 16 (2005), 645-678. Link
  15. A.K. Jain, M.N. Murty, P. J. Flynn. Data clustering: A review. ACM Computing Surveys (CSUR) , 31(3):264 - 323 (1999). Link
  16. Q. Du, V. Faber, and M. Gunzburger. Centroidal Voronoi Tesselations: Applications and Algorithms. SIAM Review, 41 (1999), 637-676. Link
  17. T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Springer-Verlag, Berlin, Germany, 2001.
  18. A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Proc. 14th Symposium on Advances in Neural Information Processing Systems, 2001. Link
  19. R. Kannan, S. Vempala, and A. Vetta, On clusterings - good, bad and spectral, in Proc. 41st Symposium on the Foundation of Computer Science(FOCS), 2000.

top