CS529 FURTHER READINGS - Spring 2018

The following list is a selection of papers related to, or extending topics covered in lectures. A (*) denotes a more challenging paper. This collection may be changing, mostly through my additions, so check it from time to time.

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 for Dynamizing Decomposable Searching Problems", Computing 26, 155-166 (1981).

3. T. Chan, "Dynamic Planar Convex Hull Operations in Near Logarithmic Amortized Time", Journal of the ACM 48, 1-12 (2001).

Optimal Output Sensitive Convex Hull.
4. D. Kirkpatrick and R. Seidel, "The Ultimate Planar Convex Hull Algorithm,", SIAM Journal of Computing 1986, 287-299 (1986), especially the lower bound.

5. T. Chan, "Optimal Output Sensitive Convex Hull Algorithms in 2 and 3 Dimensions", Discrete and Computational Geom. 16, 361-368 (1996).

6. T. Chan, "Output Sensitive Results on Convex Hulls, Extreme Points, and Related Problems", Discrete and Comp. Geom. 16, 369-387 (1996).

Segment Intersection

1. 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. These are o(n log n) algorithms.
a. R. Seidel, "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons.", Computational Geometry. Theory and Application 1, 51-64 (1991).

b. R. Tarjan and C. van Wyk. "An O(n log log n) Algorithm for Triangulating a Simple Polygon" SIAM J. on Computing 17, 143-178 (1988).

c. K. Clarkson, R. Tarjan, and C. van Wyk, "A Fast Las Vegas Algorithm for Triangulating a Simple P{olygon", 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. [This is the original proof of the art gallery theorem. 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) This has the linear-time planar algorithm for dimension d=2, general non-separated case, and the extension to d>2] C-Y Lo, J. Matousek, and W. Steiger, "Algorithms for Ham-Sandwich Cuts", Discrete and Computational Geometry, 433-452 (1994).


2. Slope Selection.

(*)(i) R. Cole, J. Salowe, W. Steiger, E. Szemeredi, "An Optimal Time Algorithm for Slope Selection", SIAM J. Comp. 18, 792-810 (1989).

(ii) An optimal randomized algorithm for slope selection (J. Matousek, "Randomized Optimal Algorithm for Slope Selection", Information Processing Letters, 39, 183-187, 1991).

3. k-sets:

(i) T. Dey, "Improved Bounds for Planar k-sets", Discrete & Computational Geometry, Vol. 19, No. 3, (1998), 373-382). [It gives an upper bound for the complexity of the k-th level of a line arrangement in the plane.

(ii) 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. S. Langerman and W. Steiger, The Complexity of Hyperplane Depth in the Plane., Discrete and Computational Geometry 30, 299-309 (2003)

Parametric Search

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

2. 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. 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) A 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. 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. (*) B. Chazelle and E. Welzl, "Quasi-Optimal Range Searching in Spaces of Finite VC Dimension", Disc. and Comp. Geom 4,, 467-489 (1989).

2. A paper about "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. 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. 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. D. Hausler and E. Welzl, "Epsilon Nets and Simplex Range Queries", Discrete and Comp. Geom. 2, 127-151 (1987)

3. "Improved Bounds on Weak Nets for Convex Sets", B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, M. Sharir, E. Welzl, Discrete Comput. Geom. 13 (1995), 1-15.

In-Place Geometric Algorithms.

1. 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. 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.