Arrangements—Techniques and Applications, Seminar, Fall 1998–1999

Seminar

Lecture: Wednesday, 17:00–19:00, Schreiber 7 note change of room

Instructor: Dan Halperin
Office hours: Wednesday, 16:00–17:00, Schreiber 114

An arrangement of geometric objects is the decomposition of space induced by these objects. An arrangement of a finite collection \(L\) of lines in the plane, for example, is the subdivision of the plane into vertices, edges, and faces induced by the lines in \(L\). Arrangements of curves and surfaces are fundamental constructs in computational geometry, and they are useful for solving problems in a variety of domains such as computer vision, robot motion planning, molecular modeling, mechanical assembly planning, and more. For a survey of definitions, problems, results and applications of arrangements [psz]

In the seminar we will cover basic techniques for manipulating arrangements, with an emphasis on applications.

After two introductory meetings, we will follow the schedule below of students presentations (temporary list, stay tuned).

by now all the dates are of course outdated; they will be revised after the strike ends

Aspect Graphs (Maintaining Invariants, Sparseness)

• 11.11
  • Efficiently computing and representing aspect graphs of polyhedral objects
    Ziv Gigus, J. Canny and Raimund Seidel, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 13. no. 6 (1991), 542–551
• 18.11
  • Sparse arrangements and the number of views of polyhedral scenes
    M. de Berg, Dan Halperin, Mark H. Overmars and Marc van Kreveld, International Journal of Computational Geometry and Applications, 7 (1997), 175–195

Geometric Modeling of Molecules (“Fatness”, Robustness I)

• 25.11
  • Spheres, molecules, and hidden surface removal
    Dan Halperin and Mark H. Overmars, In Proceedings 10^th ACM Symposium on Computational Geometry, Stony Brook, 1994, pp. 113–122
• 02.12
  • A perturbation scheme for spherical arrangements with application to molecular modeling
    Dan Halperin and Christian  R. Shelton, Proceedings of the 13^th ACM Symposium on Computational Geometry, Nice, 1997, pp. 183–192

Robot Motion Planning (Configuration Space)

• 9.12
  • Chapter 13, Robot motion planning in Computational Geometry: Algorithms and Applications
    Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, Springer, 1997
  • On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
    Klara Kedem, R. Livne, János Pach and Micha Sharir, Discrete Computational Geometry 1 (1986), pp. 59–71
• 16.12
  • Robot motion planning and the single cell problem in arrangements
    Dan Halperin, Journal of Intelligent and Robotic Systems, 11 (1994) pp. 45-–65
  • A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
    Dan Halperin and Micha Sharir, Discrete and Computational Geometry, 16 (1996), 121–134

Assembly Planning (Motion Space)

• 23.12
  • A general framework for assembly planning: The motion space approach
    Dan Halperin, J.-C. Latombe, and R. H. Wilson, Algorithmica, to appear.
• 30.12
  • Polyhedral assembly partitioning using maximally covered cells in arrangements of convex polytope
    Leo Guibas, Dan Halperin, H. Hirukawa, J.-C. Latombe, and R. H. Wilson, International Journal of Computational Geometry and Applications, 8(2), 1998, 179–199

Part Manipulation (Duality, Zone)

• 6.1.99
  • Orienting polygonal parts without sensors
    Ken Y. Goldberg, Algorithmica, 10 (1993), pp. 201–225
  • The complexity of oblivious plans for orienting and distinguishing polygonal parts
    Y.-B. Chen and D. Ierardi, Algorithmica, 14 (1995), pp. 367–397
• 13.1
  • The area bisectors of a polygon and force equilibria in programmable vector fields
    Karl F Böhringer, B.R. Donald, and Dan Halperin, Proceedings of the 13^th ACM Symposium on Computational Geometry, Nice, 1997, pp. 457–459
    The full version [psz]

Miscellaneous (3D Vertical Decomposition, Robustness II)

• 20.01
  • Vertical decompositions for triangles in 3-space
    Mark de Berg, Leo Giubas, and, Dan Halperin, Discrete and Computational Geometry, 15 (1996), 36–61
• 20.01
  • Snap rounding line segments efficiently in two and three dimensions
    M. Goodrich, Leo Guibas, J. Hershberger, and P. Tanenbaum, In Proceedings of the 13^th ACM Symposium on Computational Geometry, Nice, 1997, pp. 284–293
• 27.01
  • Robust plane sweep for intersecting segments
    J.-D. Boissonnat and Franco P. Preparata, Technical report No. 3270, INRIA, September 1997