Reading

Books and Surveys

I.F. Aurenhammer, R. Klein, and D.T. Lee. Voronoi Diagrams and Delaunay Triangulations, World Scientific, 2013.
II.B. Chazelle. The Discrepancy Method: Randomness and Complexity Cambridge Univ.Press, 2001. [C]
III.M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008. (course textbook) [BCKO]
IV.J. E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press LLC, Boca Raton, FL, 2004. [GO]
V.Sariel Har-Peled. Geometric Approximation Algorithms (Mathematical Surveys and Monographs). American Mathematical Society (2011). [HP]
VI.J. Matousek, Lectures on Discrete Geometry, Springer, 2002. [Ma]
VI.J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. North-Holland, 2000. [SU]

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

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.
  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.
  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.
  6. E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257-276, 1985.
  7. F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21:267-280, 1992.
  8. N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM , 29:669-679, 1986. [ST] Link
  9. 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. I. J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 211-219, 1995.
  2. B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992.
  3. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
  4. D. P. Dobkin, and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381-392, 1985.
  5. D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. Computing the intersection-depth of polyhedra. Algorithmica, 9:518-533, 1993.

top

Convex Hull

  1. T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 10-19, 1995.
  2. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
  3. R. Seidel. 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.
  4. R. Seidel. Small-Dimensional Linear Programming and Convex Hulls Made Easy, DCG 6 (1991) 423-434. [Sei]
  5. R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comput. Geom. Theory Appl., 5:115-116, 1995.

top

Proximity Problems

  1. 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.
  2. S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.
  3. L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992.

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.
  2. J. Matousek. Lower envelopes. Ch 7 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
  3. J. Matousek. Number of faces in arrangements. Ch 6 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.

top

Geometric Sampling

  1. P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, Geometric approximation via coresets, in Combinatorial and Computational Geometry (J. Goodman, ed.), Cambridge University Press, New York, 2005. [AHV]. Link
  2. B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000.
  3. J. Matousek. Ch. 10 in Lectures on Discrete Geometry. Springer-Verlag New York, 2002.
  4. J. Pach and P. K. Agarwal. Combinatorial Geometry, Wiley Interscience, 1995 (Chapters 15, 16).

top

Geometric Optimization

  1. P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998.
  2. 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.
  3. S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey, Math Programming, 97, 2003.
  4. R. Motwani and P. Raghavan. Ch 9 in Randomized Algorithms. Cambridge University Press, 1995.
  5. K. L. Clarkson. Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. J. ACM 42(2): 488-499 (1995) [Cla]
  6. R. C. Veltkamp, Shape matching: Similarity measures and algorithms. Tech Rept, Utrecht University, 2001.

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.
  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.
  3. T. M. Chan: Optimal Partition Trees. Discrete & Computational Geometry 47(4): 661-690 (2012).

top

High Dimensional Geometry

  1. A. Gionis, P. Indyk, R. Motwani. Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529
  2. A. Andoni, P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008)
  3. J. Matousek. Lectures on Discrete Geometry, Springer, 2002 (Chapter 15).





Home