CS529 PROJECTS - Fall '07

The following list is a selection of suggested mini-projects. There is one implementation project for 3-d arrangements. The rest are papers which you are to read, understand, and explain to me in my office. I may ask you to also present to the entire class if (i) the paper is generally interesting and (ii) you know it really well. More challenging papers are marked with an (*). This collection will be changing, mostly through my additions, so check it from time to time. If you are not enthusiastic about any of the choices, feel free to offer a suggestion of your own. BEFORE STARTING WORK, PLEASE CLEAR YOUR CHOICE WITH ME FIRST.

Implementation Projects

1. Implement the incremental algorithm to construct the arrangment of planes in 3-dimensional space and then display certain aspects of the arrangement, from certain viewpoints, so the user has visual information.

Convex Hulls

1. [Chazelles' optimal convex layers algorithm] B. Chazelle, "An Optimal Algorithm for Computing Depths and Layers", 21st Allerton Conference, 427-436 (1983).

Dynamic Convex Hull.
2. M. Overmars and J. van Leeuwen, "Two General Methods..." Computing 26, 155-166 (1981).
3. T. Chan, "Dynamic Planar Convex Hull Operations in Near Logarithmic Amortized Time", Proc. 40th IEEE Conf. on Foundations of Comp. Sci. (FOCS), 92-99 (1999). [see also JACM 48, 1-12 (2001)]
4. T. Chan, " A dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries", Proc. 1t-th SODA, 1196-1202 (2006)

Optimal Output Sensitive Convex Hull.
5. D. Kirkpatrick and R. Seidel, "The Ultimate Planar...", SIAM Journal of Computing 1986, 287-299 (1986), especially the lower bound.
6. T. Chan, "Optimal Output Sensitive Convex Hull Algs in 2 and 3 Dims", Discrete and Computational Geom. 16, 361-368 (1996).
7. T. Chan, "Output Sensitive Results on...", Discrete and Comp. Geom. 16, 369-387 (1996).

Segment Intersection

1. Explain the optimal time and space algorithm of I. Balaban, Proc. 11th ACM Symposium on Computational Geom. 211-219 (1995).
(see also In-Place Algs, below)

Polygon Triangulation

1. Explain any o(n log n) algorithm.
a. R. Seidel, "A Simple and Fast Incremental Randomized Alg....", Computational Geometry. Theory and Application 1, 51-64 (1991).
b. R. Tarjan and C. van Wyk. "An O(n log log n) Alg...." SIAM J. on Computing 17, 143-178 (1988).
c. K. Clarkson, R. Tarjan, and C. van Wyk, "A Fast Las Vegas Alg....", Discrete and Computational Geometry 4, 423-432 (1989)
d. (*) B. Chazelle, "Triangulating a Simple Polygon in Linear time", Discrete and Computational Geometry 6, 485-524 (1991). The shorter conference version of this same result might be a good place to start [B. Chazelle, (same title), Proceedings of 31st. Annual IEEE Symposium on Foundations of Computer Science (nickname = FOCS), 29-38, (1990)].

2. [Explain the original proof of the art gallery theorem, plus another related paper on art gallery problems] V. Chvatal, "A Combinatorial Theorem in Plane Geometry", J. Combinatorial Theory B 18, 39-41 (1975). For other references consult J. O'Rourke's book on art gallery problems or the chapter by Urrutia in Handbook of Computational Geometry edited by J.-R. Sack and J. Urrutia, North-Holland 2000.

Arrangements (Sweeping, duality)

1. Ham-Sandwich Cut
(i) Explain the linear-time planar algorithm in Lo, Matousek, and Steiger, "Algorithms for Ham-Sandwich Cuts", Discrete and Computational Geometry, 433-452 (1994).
(*)(ii) Explain the algorithm for general dimension in the above paper.

2. Slope Selection.
(*)(i) Explain R. Cole, J. Salowe, W. Steiger, E. Szemeredi, "An Optimal Time Algorithm for Slope Selection", SIAM J. Comp. 18, 792-810 (1989).
(ii) Explain the paper of J. Matousek giving an optimal randomized algorithm for slope selection ("Randomized Optimal Algorithm for Slope Selection", Information Processing Letters, 39, 183-187, 1991).

3. (k-sets). Explain the paper of T. Dey ("Improved Bounds for Planar k-sets", Discrete & Computational Geometry, Vol. 19, No. 3, (1998), 373-382) giving an upper bound for the complexity of the k-th level of a line arrangement in the plane, or the paper of G. Toth ("Point sets With Many k-Sets", Discrete and Computational Geometry 26, (2001) 187-194) giving a new lower bound.

4. Topologically Sweeping an Arrangement
a. The fundamental paper is H. Edelsbrunner, L. Guibas, and J. O'Rourke, "Topologically Sweeping an Arrangement", J. Computer and System Science 38, 165-194 (1989).

b. One of several applications is H. Edelsbrunner and D. Souvaine, "Computing Least Median of Squares Regression Lines and Guided Topological Sweep", J.Amer. Statist. Assoc 85, 115-119 (1990).

5. Depth in Arrangements
a. Explain the paper of S. Langerman and W. Steiger, The Complexity of Hyperplane Depth in the Plane., Discrete and Computational Geometry 30, 299-309 (2003)

Parametric Search

1. Explain P. Agarwal, B. Aronov, M. Sharir, S. Suri, "Selecting Distances in the Plane", Algorithmica 9, 495-514 (1993).

2. Explain B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, ``Diameter, Width, Closest Line Pair, and Parametric Searching'', Discrete and Comp. Geom. 10, 183-196 (1993). (1992) 120-129.

3. Explain J. Matousek, "Computing the Center of a Planar Point Set", in Discrete and Computational Geometry: Papers from the DIMACS Special Year, 221-230 Amer. Math. Soc. Providence, RI (1992) (J. Goodman, R. Pollack, W. Steiger eds.)

4. Diameter in n Points in 3-Space.
(a) The crucial reference is K. Clarkson and P. Shor, "Applications of Random Sampling in Computational Geometry II" Discrete and Computational Geometry 4, 387-421 (1989). It has several other important applications and therefore cuts across several of my categories.

This topic also involves derandomization of the above algorithm. It is not easy. Three papers are (*)

(i) J. Matousek and O. Schwartzkopf "A Deterministic Algorithm for the Three-Dimensionsl Diameter Problem", Computational Geometry: Theory and Applications 6, 253-262 (1996).

(ii) S. Bespamyatnikh, "An Efficient Algorithm for the Three-Dimensional Diameter Problem", Proc Ninth ACM-SIAM Symposium on Discrete Algs, 137-146 (1998).

(iii) E. Ramos, "An Optimal Deterministic Algorithm for Computing the Diameter of 3-D Point set", ACM Symp. on Computational Geometry, (2000) or the journal version Discrete and Comoutational Geometry 26, 233-244 (2001).

Linear Programming

1. Explain Megiddo's linear time algorithm for LP in fixed dimension (N. Megiddo, "Linear Programming in Linear Time When the Dimension is Fixed.", J.ACM 31, 114-127 (1984).

Voronoi Diagram and Delaunay Triangulation

1. Report on a topic (e.g. Voronoi Diagrams using convex distance functions) from F. Aurenhammer, "Voronoi Diagrams: A Survey of a Fundamental Geometric Data Structure", ACM Computing Surveys 23, 345-405 (1991).

2. Another randomized alg for Delaunay triangulation is the paper from the Parametric Search (diameter) Section by K. Clarkson and P. Shor. You could read it just for the Delaunay application.

3. (*?) P. Agarwal M. deBerg, J. Matousek, and O. Schwartzkopf "Constructing Levels in Arrangements and Higher Order Voronoi Diagrams", Tenth ACM Symposium on Computational Geometry, 67-75 (1994).

4. Golin, MJ and Na H.,J ``On the Average Complexity of 3D-Voronoi Diagrams of Random Points On Convex Polytopes'' Computational Geometry: Theory and Applications. 2003. 25. 197-231.

5. Golin, MJ and Na H.,J ``The ProbabilisticJ Complexity of the Voronoi DiagramJ of Points onJ a Polyhedron'', The 2002 ACM Symposium on Computational Geometry (SoCG'2002).

6. Jeff Ericson. "Nice point sets can have nasty Delaunay triangulations" Discrete & Computational Geometry 30(1):109-132, 2003.

7. Jeff Ericson "Dense point sets have sparse Delaunay triangulations", Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 125-134, 2002. (To appear in Discrete & Computational Geometry).

8. Jeff Ericson. "Uniform samples of generic surfaces have nice Delaunay triangulations ", Preprint, December 2002. (you can get this from the homepage)

Geometric Data Structures

1. (*) Explain B. Chazelle and E. Welzl, "Quasi-Optimal Range Searching in Spaces of Finite VC Dimension", Disc. and Comp. Geom 4,, 467-489 (1989).

2. Explain the paper of "Queaps", J. Iacono and S. Langerman, Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002), Vancouver, British Columbia, Canada, November 20-23, 2002. [i can get you a copy]

3. Explain the paper "Retroactive Data Structures" by E. Demaine, J. Iacono and S. Langerman, Proceedings of the ACM-SIAM Symposium On Discrete Algorithms (SODA 2004), pages 281-290, 2004.

4. Explain the paper "Proximate Point Location" by J. Iacono and S. Langerman, Proceedings of the 2003 ACM Symposium on Computational Geometry (SoCG 2003), 220-226, (2003).

5. I will put on some papers on kd-trees, quadtrees, etc.

Derandomization, Lower Bounds.

1. Read B. Chazelle and J. Friedman, "A Deterministic Veiw of Random Sampling and its Use in Geometry", Combinatorica 10, 229-249 (1990).

2. Read D. Hausler and E. Welzl, "Epsilon Nets and Simplex Range Queries", Discrete and Comp. Geom. 2, 127-151 (1987)

In-Place Geometric Algorithms.

1. Read H. Bronnimann and T. Chan, "Space Efficient Algorithms for Computing the Convex Hull", Proc. Latin American Symp. on Theoretical Informatics. LNCS 2976, 162-171 (2004)

2. Read T. Chan. "Space Efficient Algorithms for Segment Intersection", Proc 15-th Canad. Conf. on Comp. Geom. 68-71 (2003).

Some Papers about Vision.

1. Asano, Chen, Katoh, Tokuyama, "Polynomial-time solutions to image segmentation", 7th SIAM-ACM Conf of Discrete Algs, 1996, 104-113.

2. Gigus, Canny, Seidel, "Efficiently computing and representing aspect graphs of polyhedral objects", Trans. Pattern Analysis and Machine Intelligence 13, (1991) 542-551.

3. Rucklidge "Locating Objects using the Hausdorf distance", Proc 5th Int. Conf on COmputer Vision (1995) 457-464.