Reading
Books and Surveys
- F. Aurenhammer, R. Klein, and D.T. Lee. Voronoi Diagrams and Delaunay Triangulations,World Scientific, 2013.
- B. Chazelle. The Discrepancy Method: Randomness and Complexity Cambridge Univ.Press, 2001. [C]
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008. (course textbook) [BCKO]
- J. E. Goodman and J. O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press LLC, Boca Raton, FL, 2004. [GO]
- Sariel Har-peled. Geometric Approximation Algorithms (Mathematical Surveys and Monographs). American Mathematical Society (2011). [HP]
- J. Matousek, Lectures on Discrete Geometry, Springer, 2002. [Ma]
- J. O'Rourke, Computational Geometry in C, 2nd edition, Cambridge University Press, New York, 1998. [O]
- J. Pach and P. K. Agarwal, Combinatorial geometry, Wiley-Interscience, New York, 1995. [PA]
- F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985. [PS]
- J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. North-Holland, 2000. [SU]
top
Papers
- 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.
- B. Chazelle, L. J. Guibas, D.T. Lee. The Power of Geometric Duality. BIT 25 (1985), 76-90. [CGL]
- B. Chazelle and B. Rosenberg. Computing partial sums in multidimensional arrays. In Proc. 5th Annu. ACM Sympos. Comput. Geom., pp. 131-139, 1989.
- F. P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
- A. C. Yao. Decision tree complexity and Betti numbers. In Proc. 25th Annu. ACM Sympos. Theory Comput., 1994.
top
- 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.
- 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.
- B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986.
- B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications. Algorithmica, 1:163-191, 1986.
- H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15:317-340, 1986.
- E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257-276, 1985.
- K. Mehlhorn. Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag, 1984
- K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215-241, 1990.
- F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21:267-280, 1992.
- N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM , 29:669-679, 1986. [ST] Link
- 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
- I. J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 211-219, 1995.
- J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28:643-647, 1979.
- B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992.
- K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
- D. P. Dobkin, and D. G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. J. Algorithms, 6:381-392, 1985.
- D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. Computing the intersection-depth of polyhedra. Algorithmica, 9:518-533, 1993.
top
- 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.
- K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.
- 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.
- R. Seidel. Small-Dimensional Linear Programming and Convex Hulls Made Easy, DCG 6 (1991) 423-434. [Sei]
- R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comput. Geom. Theory Appl., 5:115-116, 1995.
- G. M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, 1994.
top
- 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.
- S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.
- L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992.
top
- 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.
- T. K. Dey. Improved Bounds for Planar k -Sets and Related Problems. Discrete & Computational Geometry 19(3): 373-382 (1998).
- J. Matousek. Lower envelopes. Ch 7 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
- J. Matousek. Number of faces in arrangements. Ch 6 in Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
- F. M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.
top
- 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
- N. Alon, Y. Matias, M. Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences 58 (1999): 137–147 [AMS]
- B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000.
- G. Cormode. Sketch techniques for approximate query processing, Synopses for Approximate Query Processing: Samples, Histograms, Wavelets and Sketches, Foundations and
Trends in Databases. NOW publishers, 2011 [Cor].
- P. Indyk. Streaming algorithms for geometric problems. In Proc. 24th Intl. Conf. Foundat. Software Tech. Theoret. Comput. Sci., pages 32-34, 2004.
- J. Matousek. Ch. 10 in Lectures on Discrete Geometry. Springer-Verlag New York, 2002.
- J. Matousek. Lectures on Discrete Geometry. Springer-Verlag, New York, 2002.
- S. Muthukrishnan. Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland.
- J. Pach and P. K. Agarwal. Combinatorial Geometry, Wiley Interscience, 1995 (Chapters 15, 16).
top
- 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.
- 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.
- T. M. Chan: Optimal Partition Trees. Discrete & Computational Geometry 47(4): 661-690 (2012).
- J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992.
top
- P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998.
- 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.
- S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey, Math Programming, 97, 2003.
- G. B. Dantzig. Linear Programming, (Historical Account).
- R. Motwani and P. Raghavan. Ch 9 in Randomized Algorithms. Cambridge University Press, 1995.
- K. L. Clarkson. Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. J. ACM 42(2): 488-499 (1995) [Cla]
- R. C. Veltkamp, Shape matching: Similarity measures and algorithms. Tech Rept, Utrecht University, 2001.
top
- A. Gionis, P. Indyk, R. Motwani. Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529
- A. Andoni, P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51(1): 117-122 (2008)
- J. Matousek. Lectures on Discrete Geometry, Springer, 2002 (Chapter 15).
top