Reading
Books and Surveys
- F. Aurenhammer and R. Klein. Voronoi Diagrams, CRC Press.
- 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]
- H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001. [Ed]
- 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.
- R. Seidel, M. Sharir. Top-Down Analysis of Path Compression. In SIAM J. Comp., 2005.
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. Link.[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.
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. 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.
- 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
- F. Aurenhammer and R. Klein. Voronoi diagrams. In Handbook of Computational Geometry (J.R. Sack and J. Urrutia, Eds.). North Holland, 1998.
- 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.
- J. Pach and P.K. Agarwal. Combinatorial Geometry. Wiley Interscience, 1995 (Chapters 10, 11)
- F. M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.
top
- 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.
- 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.
- H. Edelsbrunner. Triangle Meshes. Ch. 2 in Geometry and Topology for Mesh Generation. Cambridge University Press, 2001.
- 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.
- J. Remy and A. 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.
- J. Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. J. Algorithms 18(3): 548-585 (1995).
- 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.
- J. R. Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications 22(1-3):21-74, 2002.
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
- B. Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2000.
- 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.
- 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. 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.
- 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]
- 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.
- P. Besl and N. McKay. A method for registration of 3-D shapes. IEEE Trans. on Pattern Analysis and Machine Intelligence, 14 (1992).
- 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).
- 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
- R. C. Veltkamp, Shape matching: Similarity measures and algorithms. Tech Rept, Utrecht University, 2001.
- H. Wolfson and I. Rigoutsos. Geometric hashing: An overview. IEEE Computational Science and Engineering, 4 (1997), 10-21.
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