Reading

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed., 2008. (course textbook) [BCKO]
B. Chazelle. The Discrepancy Method: Randomness and Complexity Cambridge Univ. Press, 2001. [C]
S. L. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton Univ. Press, 2011. [DO]
J. E. Goodman, J. O'Rourke, C. Toth (eds.), Handbook of Discrete and Computational Geometry, 3rd edition, CRC Press LLC, Boca Raton, FL, 2017. [GO]
S. 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, Second Edition, Cambridge Univ. Press, 1998. [OR]
F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer, 1985. [PS]
G. Peyre and M. Cuturi, Computational Optimal Transport: With Applications to Data Science, Foundations and Trends in Machine Learning, 2019. [PC]
A. Khamis, R. Tsuchida, M. Tarek, V. Rolland and L. Petersson. Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024
E. F. Montesuma, F. M. N. Mboula and A. Souloumiac. Recent Advances in Optimal Transport for Machine Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025

Papers

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. [CR]

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. [Ag]
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. [AE]
B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133-162, 1986. [CG1]
H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput., 15:317-340, 1986. [EGS]
E. M. McCreight. Priority search trees. SIAM J. Comput., 14(2):257-276, 1985. [Mc]
F. P. Preparata and R. Tamassia. Efficient point location in a convex spatial cell-complex. SIAM J. Comput., 21:267-280, 1992. [PT]
N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM, 29:669-679, 1986. [ST]
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. [Sn]

I. J. Balaban. An optimal algorithm for finding segment intersections. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pp. 211-219, 1995. [Ba]
B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM, 39:1-54, 1992. [CE]
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. [CS]

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. [Ch]
K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989. [CS]
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. [Se1]
R. Seidel. Small-Dimensional Linear Programming and Convex Hulls Made Easy, Discrete Comput. Geom., 6 (1991) 423-434. [Sei2]
R. Seidel. The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comput. Geom. Theory Appl., 5:115-116, 1995. [Se3]

P. B. Callahan and S.R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest neighbors and potential fields. J. ACM, 42: 67-90, 1995. [CK]
L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica, 7:381-413, 1992. [GKS]
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. [AS]

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].
J. Pach and P. K. Agarwal. Combinatorial Geometry, Wiley Interscience, 1995 [PA] (Chapters 15, 16).
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. [Ag]
P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, Amer. Math. Soc. Press, 1998, pp. 1-56. [AE]
T. M. Chan: Optimal Partition Trees. Discrete Comput. Geom. 47(4): 661-690 (2012). [Ch2]
J. Matousek: Efficient Partition Trees. Discrete Comput. Geom. 8: 315-334 (1992). [Ma2]

P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30:412-458, 1998. [AS2]
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. [AG]
S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey, Math Programming, 97, 2003. [Ar]
K. L. Clarkson. Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small. J. ACM 42(2): 488-499 (1995) [Cl]

J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 56:222-230, 1985. [Bou]
W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math., 26:189-206, 1984. [JL]
P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. 30th Annual ACM Symposium on Theory of Computing, pages 604-613, 1998. [IM]
A. Andoni, P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Comm. ACM 51(1): 117-122 (2008).