COMPSCI 234: Computational Geometry


CPS234: COMPUTATIONAL GEOMETRY
Term: Spring 2004
Time: Tu Th 3:50pm - 5:05pm
Location: LSRC D243

Instructors:	Herbert Edelsbrunner and Alper Üngör
	featuring Yusu Wang

syllabus announcements schedule projects references

Announcements

HW#7 [ps, pdf] is out.
Please stop by D207 to pick up your graded HW4.
HW#6 [ps, pdf] is out.
HW#5 [ps, pdf] is out.
Solution for Problem 2 of HW#3 [ps, pdf] is available.
HW#4 [ps, pdf] is out.
A one-page project proposal is due on March 16.
HW#3 [ps, pdf] is out.
HW#2 [ps, pdf] is out.
HW#1 [ps, pdf] is out.
HW#0 [ps, pdf] is out.
First class is on Jan 8th.

Schedule

Date	Lecture Topic	Assignments	Speaker
Jan 8 Th	Introduction, syllabus, course structure, etc.	HW#0 out [ps, pdf]	H
	PLANE-SWEEP [BKOS00, Chapters 2 and 3 ]
Jan 13 Tu	Convex hulls Jarvis' march [J73]; divide & conquer; Graham's scan [G72, A79]; Chan's alg.[C96]		A
Jan 15 Th	Line segment intersections Plane-sweep [BO79]; optimal time [CE92]		A
Jan 20 Tu	Subdivision overlay Half-edge data structure [CGAL] map overlays, intersection, union, difference [BKOS00]		A
Jan 22 Th	Polygon triangulation Art galleries [C83]; partitioning simple polygons [LP77]; triangulating monotone polygons [GJPT78]	HW#1 out [ps, pdf]	A
	ORTHOGONAL SEARCH [BKOS00, Chapters 5 and 10]
Jan 29 Th	Range search Quad-tree; kd-tree [B75]; range tree; fractional cascading [CG86]		H
Feb 3 Tu	Geometric data structures Segment tree [B77]; interval tree [E83]; priority search tree [M85]	HW#1 due	H
Feb 5 Th	Box intersection Plane-sweep [E83]; streaming [EO85]; fixed-radius near neighbors; bounding boxes	HW#2 out [ps, pdf]	H
	POINT LOCATION [BKOS00, Chapters 6 and 7] [Sno97]
Feb 10 Tu	Kirkpatrick hierarchy Point-in-polygon; planar subdivision; Kirkpatrick hierarchy [Kir83]		Y
Feb 12 Th	Seach trees Slab method; separating chain tree [EGS86]; persistent search tree [ST86]		Y
Feb 17 Tu	Open problems session Empty convex k-gon; repeated distances (min, unit, convex); optimal triangulations	HW#2 due	A,H,Y
Feb 19 Th	Voronoi diagrams Voronoi diagrams [AK00]; largest empty disk; Fortune's algorithm	HW#3 out [ps, pdf]	Y
	DELAUNAY TRIANGULATIONS [BKOS00, Chapter 9]
Feb 24 Tu	Edge-flip algorithm Empty circles, local Delaunayhood [D34], edge-flip [L77], lifting, analysis, maxmin angles		A
Feb 26 Th	Randomized incremental algorithm Incremental construction [CKS92]; backward analysis [S93]		A
Mar 2 Tu	Delaunay refinement Steiner triangulation [BS95]; quality measure; quad-trees [BS95]; circumcenter insertion [R95]; local feature size	HW#3 due	A
Mar 4 Th	Open problems session Shelling; space-filling tetrahedra [S81]; space-tiling acute tetrahedra [ESU04]	HW#4 out [ps, pdf]	A,H
Mar 9 Tu	SPRING BREAK
Mar 11 Th	SPRING BREAK
Mar 16 Tu	Project proposal discussion	Proposal due	A
	SURFACE TOPOLOGY [E01, Chapter 4]
Mar 18 Th	Triangulated surfaces 2-manifolds (with and without boundary); triangulations; embeddings; Euler characteristic.		H
Mar 23 Tu	Surface simplification Edge contraction [GH97]; topology preservation [DEGN99]; barycentric coordinates; simplicial maps; simplification.	HW#4 due	H
Mar 25 Th	Error measure Fundamental quadric [GH97]; eigenvalues and eigenvectors.	HW#5 out	H
	ARRANGEMENTS [BKOS00, Chapter 8]
Mar 30 Tu	Zones Duality; line arrangements; complexity; incremental algorithm; zone theorem [ESS93]		A
Apr 1 Th	Levels and discrepancy Super-sampling for rendering; Half-plane discrepancy		A
Apr 6 Tu	Topological sweep Ordinary lines [KM58], pseudoline arrangements [G73], zone trees, amortized analysis [EG89]	HW#5 due HW#6 out	H
	DIFFERENTIAL TOPOLOGY
Apr 8 Th	Morse functions Smooth functions, critical points, piecewise linear functions, ascending manifolds [EHZ03]		H
Apr 13 Tu	Reeb graphs Loops, orientable and non-orientable 2-manifolds, algorithm [CEHNP04]		H
Apr 15 Th	Pairing critical points Chain complex, homology groups, filtration	HW#6 due	H
Apr 23 Fr	Final Exam (take-home)
Apr 29 Th	Projects Due

References

Books

[BKOS00] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000. [course textbook]

[E01] H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.

Surveys

[BE95] M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry (2nd ed.), D.-Z. Du and F. Hwang (eds.), World Scientific, 1995, 47-123.
[E00] H. Edelsbrunner. Triangulations and meshes in computational geometry. Acta Numerica (2000), 133-213.
[S81] M. Senechal. Which tetrahedra fill space? Math. Mag. 54 (1981), 227-243.

[Sno97] J. Snoeyink. Point location. Handbook of discrete and computational geometry, CRC Press, 1997, 559-574.
Other Papers

[A79] A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9:216-219, 1979. [A left-to-right variant of Graham's scan]

[AK00] F. Aurenhammer and R. Klein. Voronoi Diagrams. Handbook of Computational Geometry, Ed. J. Sack, J. Urrutia (eds.), 2000, 201-290.

[B75] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18:509-517, 1975.

[B75] J. L. Bentley. Solution to Klee's rectangle problems. Tech. Rep., Carnegie-Mellon Univ., Pittsburgh, 1975.

[BO79] J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28:643-647, 1979.

[C96] T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, 16:361-368, 1996.

[CE92] B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM 39:1-54, 1992.

[CG86] B. Chazelle and L. J. Guibas. Fractional cascading. Algorithmica 1:133-162 and 163-191, 1986.

[C83] V. Chvatal. A combinatorial theorem in plane geometry. J. Combin. Theory Ser. B 18:39-41, 1975.

[CEHNP04] K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan and V. Pascucci. Loops in Reeb graphs of 2-manifolds. Discrete and Computational Geometry, to appear.
[D34] B. N. Delaunay. Sur la Sphere vide. Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk 7:793-800, 1934.

[DEGN99] T. K. Dey, H. Edelsbrunner, S. Guha and D. V. Nekhayev. Topology preserving edge contraction. Publications de l'Institut Mathematique (Beograd) (N. S.) 66:23-45, 1999.

[E83] H. Edelsbrunner. A new approach to rectangle intersections. International Journal Computational Mathematics 13:209-219 and 221-229, 1983.

[EG89] H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. Journal Computer and System Sciences 38:165-194, 1989. Corrigendum. Journal Computer and System Sciences 42:249-251, 1991.

[EGS86] H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing 15:317-340, 1986.

[EHZ03] H. Edelsbrunner, J. Harer and A. Zomorodian. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry 30:87-107, 2003.

[EO85] H. Edelsbrunner and M. H. Overmars. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms 6:515-542, 1985.

[ESS93] H. Edelsbrunner, R. Seidel and M. Sharir. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing 22:418-429, 1993.

[ESU04] D. Eppstein, J. Sullivan and A. Üngör. Computational Geometry: Theory and Applications, 27:237-255, 2004. >/tr>
[GJPT78] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Information Processing Letters, 7:175-179, 1978.

[GH97] M. Garland and P. S. Heckbert. Surface simplification using quadratic error metrics. Computer Graphics, Proc. SIGGRAPH, 209-216, 1997.

[G72] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972.

[G72] B. Grunbaum. Arrangements and Spreads. American Mathematical Society, Providence, Rhode Island, 1972.

[GKS92] L. J. Guibas, D. E. Knuth, M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7:381-413, 1992.

[J73] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18-21, 1973.

[KM58] L. M. Kelly and W. O. J. Moser. On the number of ordinary lines deternined by n points. Canadian Journal Mathematics, 10:210-219, 1958.

[Kir83] D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Computing, 12:28-35, 1983.

[L77] C. L. Lawson. Software for C1 surface interpolation. Mathematical Software III, J. Rice ed., Academic Press, New York, 1977, 161-194.

[LP77] D. T. Lee and F. P. Preparata. Location of a point in a planar subdivision and its applications. SIAM J. Computing, 6:594-606, 1977.

[M85] E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14:257-276, 1985.

[NP82] J. Nievergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures. Communications of the ACM, 25:739-747, 1982.

[R95] J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms, 18:548-585, 1995.

[ST86] N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669-679, 1986.

[S93] R. Seidel. Backward analysis of randomized geometric algorithms. New Trends in Computational Geometry, J. Pach ed., Springer-Verlag, Berlin, 37-67, 1993.

Projects

Coming soon

syllabus announcements schedule projects references

Alper Üngör (ungor@cs.duke.edu) January 2004

[BKOS00]	M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000. [course textbook]
[E01]	H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001.

[BE95]	M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry (2nd ed.), D.-Z. Du and F. Hwang (eds.), World Scientific, 1995, 47-123.
[E00]	H. Edelsbrunner. Triangulations and meshes in computational geometry. Acta Numerica (2000), 133-213.
[S81]	M. Senechal. Which tetrahedra fill space? Math. Mag. 54 (1981), 227-243.
[Sno97]	J. Snoeyink. Point location. Handbook of discrete and computational geometry, CRC Press, 1997, 559-574.

[A79]	A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters, 9:216-219, 1979. [A left-to-right variant of Graham's scan]
[AK00]	F. Aurenhammer and R. Klein. Voronoi Diagrams. Handbook of Computational Geometry, Ed. J. Sack, J. Urrutia (eds.), 2000, 201-290.
[B75]	J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18:509-517, 1975.
[B75]	J. L. Bentley. Solution to Klee's rectangle problems. Tech. Rep., Carnegie-Mellon Univ., Pittsburgh, 1975.
[BO79]	J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28:643-647, 1979.
[C96]	T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, 16:361-368, 1996.
[CE92]	B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM 39:1-54, 1992.
[CG86]	B. Chazelle and L. J. Guibas. Fractional cascading. Algorithmica 1:133-162 and 163-191, 1986.
[C83]	V. Chvatal. A combinatorial theorem in plane geometry. J. Combin. Theory Ser. B 18:39-41, 1975.
[CEHNP04]	K. Cole-McLaughlin, H. Edelsbrunner, J. Harer, V. Natarajan and V. Pascucci. Loops in Reeb graphs of 2-manifolds. Discrete and Computational Geometry, to appear.
[D34]	B. N. Delaunay. Sur la Sphere vide. Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk 7:793-800, 1934.
[DEGN99]	T. K. Dey, H. Edelsbrunner, S. Guha and D. V. Nekhayev. Topology preserving edge contraction. Publications de l'Institut Mathematique (Beograd) (N. S.) 66:23-45, 1999.
[E83]	H. Edelsbrunner. A new approach to rectangle intersections. International Journal Computational Mathematics 13:209-219 and 221-229, 1983.
[EG89]	H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. Journal Computer and System Sciences 38:165-194, 1989. Corrigendum. Journal Computer and System Sciences 42:249-251, 1991.
[EGS86]	H. Edelsbrunner, L. J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing 15:317-340, 1986.
[EHZ03]	H. Edelsbrunner, J. Harer and A. Zomorodian. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete and Computational Geometry 30:87-107, 2003.
[EO85]	H. Edelsbrunner and M. H. Overmars. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms 6:515-542, 1985.
[ESS93]	H. Edelsbrunner, R. Seidel and M. Sharir. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing 22:418-429, 1993.
[ESU04]	D. Eppstein, J. Sullivan and A. Üngör. Computational Geometry: Theory and Applications, 27:237-255, 2004. >/tr>
[GJPT78]	M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan. Triangulating a simple polygon. Information Processing Letters, 7:175-179, 1978.
[GH97]	M. Garland and P. S. Heckbert. Surface simplification using quadratic error metrics. Computer Graphics, Proc. SIGGRAPH, 209-216, 1997.
[G72]	R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132-133, 1972.
[G72]	B. Grunbaum. Arrangements and Spreads. American Mathematical Society, Providence, Rhode Island, 1972.
[GKS92]	L. J. Guibas, D. E. Knuth, M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7:381-413, 1992.
[J73]	R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2:18-21, 1973.
[KM58]	L. M. Kelly and W. O. J. Moser. On the number of ordinary lines deternined by n points. Canadian Journal Mathematics, 10:210-219, 1958.
[Kir83]	D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Computing, 12:28-35, 1983.
[L77]	C. L. Lawson. Software for C1 surface interpolation. Mathematical Software III, J. Rice ed., Academic Press, New York, 1977, 161-194.
[LP77]	D. T. Lee and F. P. Preparata. Location of a point in a planar subdivision and its applications. SIAM J. Computing, 6:594-606, 1977.
[M85]	E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14:257-276, 1985.
[NP82]	J. Nievergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures. Communications of the ACM, 25:739-747, 1982.
[R95]	J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation. Journal of Algorithms, 18:548-585, 1995.
[ST86]	N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669-679, 1986.
[S93]	R. Seidel. Backward analysis of randomized geometric algorithms. New Trends in Computational Geometry, J. Pach ed., Springer-Verlag, Berlin, 37-67, 1993.

CPS234: COMPUTATIONAL GEOMETRY

Announcements

Schedule

References

Projects